27. Remove Element

難易度 : Easy

Link

題目給予一個int的array : nums與一個目標int值 : val

要求將陣列中的val值都移除掉(?)並且回傳最後移除後的陣列長度

並且我們不需要在意最後陣列內各個元素的排列順序

ex :

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).

如上所示，移除掉2之後的元素僅剩0,1,4,0,3

並且我們不需要在意這5個值的排列順序

也就是說

回傳的值是5 ( 代表移除後所剩餘的元素數量)

並且不論陣列內前5個值是 0,1,4,0,3 或是 3,0,4,0,1都是可以通過的

題目還有額外的要求

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

我們不可以使用額外的空間來存放值，必須要用原本的array原地處理

這題我最開始的想法是使用雙重for來處理

雖然有成功的accepted

但是效能實在慘

因此改以一個for迴圈裡包含兩個index來動態實現的作法

原理是一次使用兩個指針 fastIndex、slowIndex

fastIndex是用來判斷目前掃描到的目標是否為val 相當於雙層for迴圈中的最外層那個

slowIndex是用來紀錄需要複寫值的位置

當nums[fastIndex] != val 時

將 nums[slowIndex]的值覆蓋成nums[fastIndex]的值

並且將slowIndex+1

當nums[fastIndex] = val 時

不將nums[slowIndex]的值覆蓋 因為不需要將val值再往更前移動

寫成code的話像這樣子

class Solution {
        public int removeElement(int[] nums, int val) {
            int fastIndex=0,slowIndex=0;
            for(slowIndex=0;fastIndex<nums.length;fastIndex++) 
            {
                if(nums[fastIndex]==val) 
                {
                    //不交換 因為不需要把val值再往前移
                }
                else 
                {
                    //交換
                    nums[slowIndex]=nums[fastIndex];
                    slowIndex++;
                }
            }
            return slowIndex;
        }
    }