未分類

Remove Duplicates from Sorted Array

Array, Go, LeetCode, TwoPointers

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

Example:

1
2
3
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
提示 解題應用
Array Sort/Merge/Move Elements

Default:

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

解答思路:

這題不但要回傳不重覆數組的長度之外，你也需要將這些重覆的數字從數組中移除，不過這個數組就不需要回傳，這邊長度還滿容易想到的，因為數組已經是排序好的，所以只要比對是不是和下一個相同就可以算出總共有多少個相異的數字，問題是需要將重覆的數字移除，這邊的移除是要將空下來的位置一一遞補，所以會有可觀的操作在這邊，看是要塞極大值後做排序，還是將array拆解去掉不要的部分後合併成新的array或者用選擇的方式把後面有存數字的位置直接與空的部分做交換，至少我想到的來說，最後者比較妥當些。

程式碼解說:

這邊我拆成兩部分來解答，一開始先走訪整個array，對比前後數字是否重覆來算出整個array有多少個相異的數字，同時將那些重覆的值塞入一個極大值，這邊也可以放極小值，總之就是需要一個標示來告知這些在array之中是不需要的空間

1
2
3
4
5
6
7
8
9
10
var count int
tmp := math.MaxInt32
for i, v := range nums {
	if tmp != v {
		tmp = v
		count++
	} else {
		nums[i] = math.MaxInt32
	}
}

再來就是處理重覆的數字，這邊我先以一個回圈做檢查，如果發現到是極大值的話就再進一個回圈並從該處開始遍歷在其之後所有的值，直到發現有非極大值也就是我們的目標後，與外層回圈找到的極大值兩個位置的值做交換，雖然是說交換不過我就直接把原本目標位置的值再塞一個極大值進去而已，之後再回到外層的回圈繼續檢查，最後因為我們已經知道有多少個彼此相異的數字，所以只要檢查到索引值+1就可以停了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
	}
}

完整程式碼:

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
func removeDuplicates(nums []int) int {
	var count int
	tmp := math.MaxInt32
	for i, v := range nums {
		if tmp != v {
			tmp = v
			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
}

總結:

欲刪除一陣列中重覆的值可先遍歷一次對照前後是否相同算出彼此相異的數字有多少個，同時將相同的值賦予標示，例如極大值後排序或者特定值後做簡易選擇交換，端看出題方式甚至能重組陣列來達成目標。

分享到