【LeetCode】27.移除元素

2021 年 7 月 31 日
筆記
leetcode, 雙指針, 數組

27.移除元素

知識點：數組；雙指針；

題目描述

給你一個數組 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，並返回移除後數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並原地修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

示例1

輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。你不需要考慮數組中超出新長度後面的元素。例如，函數返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。

示例2

輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮數組中超出新長度後面的元素。

解法一：左雙指針

這道題可以用和283題一模一樣的方法去做，都是在移動一個指定元素，將不等於這個元素的都移動到最前面就可以了；

class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != val){
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
}

時間複雜度：O(N);但是我們有兩個指針從左到右，最差情況需要遍歷兩次數組；

解法二：首尾雙指針

這道題和之前的283題中有一個區別：這道題目不用保持相對順序；也就是把不等於val的值都移動到最前面就可以了，不用管它們之間的順序。
遇到這種不用保持相對順序的往往就不需要從前向後了，可以用首尾雙指針，類似於快速排序；首指針逐漸增大，遇到等於val的停下，尾指針不斷減小，遇到不等於val的停下，然後兩者互換，然後接着走，直到兩個指針碰面，這就相當於把數組遍歷完了。

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0) return 0;  //邊界條件
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            while(left < right && nums[left] != val){
                left++;
            }
            while(left < right && nums[right] == val){
                right--;
            }
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        if(nums[left] == val) return left;     
        //首尾雙指針的時候常在最後用到的判斷方法，判斷停下來的時候是落在哪了，如果落在不等於val值上，那要加1；如果等於val的時候，那就正好；
        else return left+1;
    }
}

時間複雜度：O(N);但是這種首尾指針碰頭的方法，最多只需要遍歷一次數組；

體會

快速排序的首尾雙指針碰面的想法經常用到，這樣可以有效的減少遍曆數組的次數；
如果是要保持相對位置，那就只能從左到右，用左雙指針；如果對相對順序沒有要求，那麼就可以從兩邊開始，然後根據題目要求去交換首尾指針指向的元素。

Tags: leetcode 雙指針數組