【數組】leetcode——移除元素

2021 年 2 月 3 日
筆記
leetcode, 雙指針, 數組

編號：27. 移除元素

給你一個數組 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，並返回移除後數組的新長度。

不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並「原地」修改輸入數組。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

示例 1:
給定 nums = [3,2,2,3], val = 3,
函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。
你不需要考慮數組中超出新長度後面的元素。

示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。

思路

首先是數組元素在內存地址中是連續的，不能直接刪除，需要覆蓋。而且題目說了不需要考慮數組超出新長度後面的元素。因此我們很容易想到暴力解法。

暴力解法

使用兩層for循環，外層for循環遍曆數組，內層for循環更新數組，當nums[i]==val，將後面的數組元素往前一位進行覆蓋，同時數組長度-1。

具體代碼如下：

func removeElement(nums []int, val int) int {
	length := len(nums)
	for i := 0; i < length; i++ {
		if nums[i] == val { //找到了目標值，將後續的數組元素往前進行覆蓋
			for j := i + 1; j < length; j++ {
				nums[j-1] = nums[j]
			}
			i-- //因為數組後續值覆蓋了，所以需要在當前位繼續進行判斷nums[i]?=val
			length-- //數組長度-1
		}
	}
	return length
}

可以了解到，暴力解法的時間複雜度為O(n²)，空間複雜度為O(1)

下面介紹一種更為便捷的方法，雙指針法：「通過一個快指針和慢指針在一個for循環下完成兩個for循環的工作」雙指針法在數組和鏈表的操作中是非常常見的，很多考察數組和鏈表操作的面試題，都使用雙指針法。

雙指針法

一開始慢指針slowIndex和快指針fastIndex同時指向數組第0個元素，快指針fastIndex開始遍曆數組，如果快指針指向的元素不為val，則nums[slowIndex]=nums[fastIndex]，並且slowIndex++。最後返回的slowIndex值就是數組刪去元素val的新長度。(這裡引用了公眾號【代碼隨想錄】的動圖，比較方便直觀。)

具體代碼如下：

func removeElement(nums []int,val int) int{
    slowIndex := 0
    for fastIndex := 0;fastIndex<len(nums);fastIndex++{
        if val != nums[fastIndex]{
            nums[slowIndex] = nums[fastIndex]
            slowIndex++
        }
    }
    return slowIndex
}

Tags: leetcode 雙指針數組