Leetcode 27. 移除陣列中的指定元素

題目

先看題目。

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

翻譯成中文，給定一個整數陣列 nums 與一個整數 val，原地移除 nums 中所有出現 val 的值。元素的順序可能會改變。回傳 nums 中，不等於 val 之元素數量。

測資

測資一

+ Input: nums = [3,2,2,3], val = 3
+ Output: 2, nums = [2,2,_,_]
- Explanation: Your function should return k = 2, with the first two elements of nums being 2.
- It does not matter what you leave beyond the returned k (hence they are underscores).

測資二

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

題目文謅謅的，但其實非常好理解。我們先看測資，測資的第一筆，傳入 nums 及 val，當 val 為 3 時，移除掉 3，且將沒有 3 的部分，用原地演算法將其他元素前移。最後回傳 index 為幾時，前 index 的值不等於 3。簡單來說直接回傳其長度即可。

這邊需要注意的事情，直接存一個 counter 去數哪些值沒有 3，沒有 3 的就 counter++ 是不行的，因為 LeetCode 系統會去判斷原來的 nums 有沒有被修改，沒有就會出錯。LeetCode 會透過已修改的 nums 及答題者回傳的值去做比對。

第一種寫法（指標寫法）

class Solution {
    public int removeElement(int[] nums, int val) {
        int position = 0;

        for (int i = 0; i < nums.length; i++){
            if (nums[i] != val){
                if (position != i){
                    nums[position] = nums[i];
                }
                position += 1;
            }
        }

        return position;
    }
}

思路

一開始的想法，如同 26 題，我先比對，然後設定成 -100，再用一個迴圈往前移，但這不是個好方法，我們就不細講了。

1. 宣告一個變數為 position，紀錄要存的位置。
2. 遍歷 nums，其 i = 0~nums.length。
3. 如果 nums[i] 為 val，則跳過。如果不是，判斷 position 與 i 是否相同（這個目的是為了防止第一次相等就取代）。如果不是，將 nums[i] 放入 nums[position] 並取代，並 position++。
4. 返回 position。

過程

i = 0：nums[0] 不等於 2，position == i 不用搬，position 前進

$[ \underset{\underset{\triangle}{p}}{\mathstrut 0}, 1, 2, 2, 3, 0, 4, 2 ]$

i = 1：nums[1] 不等於 2，position == i 不用搬，position 前進

$[ 0, \underset{\underset{\triangle}{p}}{\mathstrut 1}, 2, 2, 3, 0, 4, 2 ]$

i = 2：nums[2] 等於 2，跳過，position 停在原地

$[ 0, 1, \underset{\underset{\triangle}{p}}{\mathstrut 2}, 2, 3, 0, 4, 2 ]$

i = 3：nums[3] 等於 2，跳過，position 停在原地

$[ 0, 1, \underset{p}{2}, \underset{\triangle}{2}, 3, 0, 4, 2 ]$

i = 4：nums[4] 不等於 2，把 3 寫到 nums[2]，position 前進

$[ 0, 1, \underset{p}{2}, 2, \underset{\triangle}{3}, 0, 4, 2 ]$

i = 5：nums[5] 不等於 2，把 0 寫到 nums[3]，position 前進

$[ 0, 1, 3, \underset{p}{2}, 3, \underset{\triangle}{0}, 4, 2 ]$

i = 6：nums[6] 不等於 2，把 4 寫到 nums[4]，position 前進

$[ 0, 1, 3, 0, \underset{p}{3}, 0, \underset{\triangle}{4}, 2 ]$

i = 7：nums[7] 等於 2，跳過，position 停在原地

$[ 0, 1, 3, 0, 4, \underset{p}{0}, 4, \underset{\triangle}{2} ]$

迴圈結束：position = 5，回傳 5，前 5 個元素為 0, 1, 3, 0, 4

$[ 0, 1, 3, 0, 4, \underset{p}{0}, 4, 2 ]$

時間複雜度: O(n) 空間複雜度: O(1)

提交結果

相關文章

《Leetcode 26. 移除已排序陣列中的重複項》

《Leetcode 1768. 交替合併字串》