未分類

Remove Duplicates from Sorted Array II

Array, Go, LeetCode, TwoPointers

Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example:

1
2
3
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
提示 解題應用
Array Array/Slice
TwoPointers 紀錄index位置

Default:

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

解答思路:

建議可以先參考先前Remove Duplicates from Sorted Array的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼做修改而已，如果能移除重覆的元素，當然最多要保留相同元素就不會太困難。

一開始一樣先遍歷一次對照前後是否相同，如果相同再判斷是否已經重覆超過2個以上，並一邊算出最後陣列的長度多少個(超過2個重覆就只以2個計算)，同時將超過2個以上多餘的相同值賦予標示，例如極大值後做簡易選擇交換便能達成目標。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，因為這次最多能重覆1個值，所以就需要在第一次遍歷的時候稍做修改，這邊以一個boolean值來註記是否已經出現了兩次，如果遍歷到的值與上一個不相同就重設註記為false，如果發現與先前相同但尚未重覆超過2個(註記為false)時，就將註記改為true並將最後陣列長度的計數+1(因為最多能包含一個重覆值)，而如果重覆已經超過2個便將該值賦予極大值做為標示，最後則是與先前一樣將極大值做簡易選擇交換篩至後頭即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var twice bool
var count int
tmp := math.MaxInt32
for i, v := range nums {
	if tmp != v {
		tmp = v
		twice = false
		count++
	} else if !twice {
		twice = true
		count++
	} else {
		nums[i] = math.MaxInt32
	}
}

完整程式碼:

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
func removeDuplicates(nums []int) int {
	var twice bool
	var count int
	tmp := math.MaxInt32
	for i, v := range nums {
		if tmp != v {
			tmp = v
			twice = false
			count++
		} else if !twice {
			twice = true
			count++
		} else {
			nums[i] = math.MaxInt32
		}
	}
	for i, v := range nums {
		if v == math.MaxInt32 {
			for j, vv := range nums[i+1:] {
				if vv != math.MaxInt32 {
					nums[i] = vv
					nums[i+j+1] = math.MaxInt32
					break
				}
			}
		}
		if i+1 == count {
			break
		}
	}
	return count
}

總結:

建議可以先參考先前Remove Duplicates from Sorted Array的解法，解說較為詳細，基本上概念完全一樣，欲刪除一陣列中超過2個以上多餘的重覆值，可先遍歷一次對照前後是否相同，如果相同再判斷是否已經重覆超過2個以上，並一邊算出最後陣列的長度多少個(超過2個重覆就只以2個計算)，同時將超過2個以上多餘的相同值賦予標示，例如極大值後做簡易選擇交換便能達成目標。

分享到