jotting

ⓁⒸ ‧‧‧ 283. Move Zeroes

Posted on | Post modified | In
移動零

283. Move Zeroes 移動零

❀ Origin

Problem

Given an array nums,
write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

Example

1
2
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

❀ 翻譯

問題

給定一個陣列 nums ,
寫一個函數去移動所有的 0 到最後面, 且過程中保持非零元素的相對順序.

注意

  1. 你必須在不製作一個複製陣列的情況下, 就以此操作.
  2. 最小化所有的操作數.

❀ Solution

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

/**
 * 移動所有的零到陣列最後面, 且不能新建多的陣列.
 *
 * 思路為遍歷每個元素,
 * 如果遇到 0 , 就忽略
 *
 * 遇到不是 0 ,
 * 就將該元素 nums[i] 的值放到 nums[position],
 * 並將 position + 1
 *
 * 以次類推,
 * nums 全部遍歷完之後,
 * 全部非零元素就會依照原本順序, 排在陣列最前面了.
 *
 * 之後再從該陣列位置的 position 為起始,
 * 將後面的值改成 0 , 即可.
 *
 * 例如：
 * position = 0, i = 0,
 * [0, 1, 0, 3, 12],
 * nums[i] = 0, 忽略
 *
 * position = 0, i = 1,
 * [0, 1, 0, 3, 12],
 * nums[i] = 1,
 * nums[position] = nums[i]
 * [1, 1, 0, 3, 12]
 * position + 1
 *
 * position = 1, i = 2,
 * [1, 1, 0, 3, 12],
 * nums[i] = 0, 忽略
 *
 * position = 1, i = 3,
 * [1, 1, 0, 3, 12],
 * nums[i] = 3,
 * nums[position] = nums[i]
 * [1, 3, 0, 3, 12]
 * position + 1
 *
 * position = 2, i = 4,
 * [1, 3, 0, 3, 12],
 * nums[i] = 12,
 * nums[position] = nums[i]
 * [1, 3, 12, 3, 12]
 * position + 1
 *
 * 最後將陣列從 position 開始後的元素都置換成 0
 *
 */
var moveZeroes = function(nums) {
	let position = 0,
		len = nums.length;

	for (let i = 0; i < len; i++) {
		if (nums[i] !== 0) {
			nums[position] = nums[i];
			position++;
		}
	}

	for (let i = position; i < len; i++) {
		nums[i] = 0;
	}
	// return nums;
};
// console.log(moveZeroes([0, 1, 0, 3, 12]));

JavaScript II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

/**
 * 第二種寫法,
 * 比較直覺,
 * 遇到零, 抓出來往後丟
 *
 * 從後面開始遍歷,
 * 如果 nums[i] === 0
 * 便將該位置移除 ( nums.splice(i, 1) ),
 * 最後面推一個 0 回去.
 *
 * 注意：
 * 不能從頭開始找,
 * 因為從頭的話, splice 後會刪除一個元素, 之後 push 加到最後,
 * 這樣又照著遍歷跑時, 有一個元素會被忽略
 *
 * 譬如
 * i = 0 [0, 0, 1] -> [0, 1, 0]
 * i = 1 [0, 1, 0] -> [0, 1, 0]
 *
 * 連續的第二個也是零的話就會被忽略了
 *
 */
var moveZeroes = function(nums) {
	for (let i = nums.length; i >= 0; i--) {
		if (nums[i] === 0) {
			nums.splice(i, 1);
			nums.push(0);
		}
	}
	// return nums;
};
// console.log(moveZeroes([0, 0, 1]));

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func moveZeroes2(nums []int) {

	var position, lengthNums int
	lengthNums = len(nums)

	for _, v := range nums {
		if v != 0 {
			nums[position] = v
			position++
		}
	}

	for i := position; i < lengthNums; i++ {
		nums[i] = 0
	}

}

Golang II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

func moveZeroes(nums []int) {

	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] == 0 {
			// Golang - remove element in a array 
			// 參考：https://stackoverflow.com/questions/25025409/delete-element-in-a-slice
			// 將 nums 用 append 置換
			// 假設要移除的位置 i ， 以 i 將陣列分成頭尾兩部分
			// 再將其用 append 組合起來。
			nums = append(nums[:i], nums[i+1:]...)
			nums = append(nums, 0)
		}
	}

}