未分類

Move Zeroes

Array, Go, LeetCode, Math, TwoPointers

Move Zeroes

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.

For example:

1
Given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.
提示 解題應用
TwoPointers Index Value

Default:

1
2
3
func moveZeroes(nums []int)  {
}

解答思路:

最初想使用bubble sort或直接將0的元素從最後頭位置互換，可惜此題除了0之外的其它元素還要保留相對位置，所以就改用其它方式來處理，當發現元素為0時先暫存其index值，直到發現下一個非0的元素才互換位置，最後才從原本發現0位置的下一項繼續重覆上述動作。

程式碼解說:

首先以一flag值來表示目前遍歷陣列所到達的位置，直到其index值超出陣列為止，此時一邊一一確認是否該元素的值為0且先前取出的元素都不為0，如果是的話就記錄0的位置並確認0存在，接著便繼續往下並再次確認是否先前有0存在且這次值不為0，如果也符合條件的話，就可以將先前記錄index位置的0與此index位置的其值互換，最後記得將zero改回false，並把flag值指回原本發現值為0的index位置，繼續再重新尋找下一個值為0的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var zero bool
var zeroIndex int
var flag int
for flag != len(nums) {
	if !zero && nums[flag] == 0 {
		zero = true
		zeroIndex = flag
	} else if zero && nums[flag] != 0 {
		zero = false
		nums[zeroIndex] = nums[flag]
		nums[flag] = 0
		flag = zeroIndex
	}
	flag++
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func moveZeroes(nums []int) {
	var zero bool
	var zeroIndex int
	var flag int
	for flag != len(nums) {
		if !zero && nums[flag] == 0 {
			zero = true
			zeroIndex = flag
		} else if zero && nums[flag] != 0 {
			zero = false
			nums[zeroIndex] = nums[flag]
			nums[flag] = 0
			flag = zeroIndex
		}
		flag++
	}
}

總結:

在一陣列中如需要將特定元素移至最後頭，若不需在意原本陣列值的相對位置，可使用bubble sort或直接將特定元素與最後頭儲存的值互換。若要考量相對位置的關係則可以先暫存其特定元素的index值，直到發現下一個非該元素才互換位置，並從原本該index值的下一項繼續檢查並重覆上述動作。

分享到