未分類

Remove Element

Array, Go, LeetCode, TwoPointers

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

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

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

1
2
3
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
提示 解題應用
Array Merge/Move Elements

Default:

1
2
3
func removeElement(nums []int, val int) int {
}

解答思路:

此題和先前文章的Remove Duplicates from Sorted Array思路太過類似所以內容就大部分照貼。

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

程式碼解說:

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

1
2
3
4
5
6
7
8
var count int
for i, v := range nums {
	if v != val {
		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
func removeElement(nums []int, val int) int {
	var count int
	for i, v := range nums {
		if v != val {
			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
}

總結:

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

分享到