Contents

[Golang][Leetcode][Array]刷題系列-27-Two Pointers


27. Remove Element


Level : Easy

原題連結 : Click

題目 :

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example :

Note

Input: nums = [0,1,2,2,3,0,4,2], val = 2

Output: 5, nums = [0,1,4,0,3,,,_]

Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.

Note that the five elements can be returned in any order.

It does not matter what you leave beyond the returned k (hence they are underscores).


以下是我自己的解法 - O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Remove Element.

解題思路 :

這是一個一般Two pointers的題目

  • 首先判斷他的要求需要modifying the input array in-place,也就是只能用O(1)的extra memory
  • 他說要取得拿掉given val以後新array的長度
  • 也就是說我可以將given val以外的elements往前放並回傳最後有幾個element

而這題我的實現方法是 :

  1. 我們可以將它想成有兩個pointer,一個fastIndex,一個slowIndex
  2. fastIndex是作為遍歷檢查的pointer,會檢查len(nums)次
  3. slowIndex只要沒有遇到val就會一直前進,遇到val就不前進,直到fastIndex下次與他交換,將val換走。
  4. 每一round,fastIndex都必須往前走不會停下來且檢查是否與slowIndex做值交換,只有在當fastIndex指到的值為val時才不進行交換
  5. 所以只要fastIndex走到底,代表每一個在nums裡element都已經被檢查過了
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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


最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!