LeetcCode 27：移除元素 Remove Element（python、java）

公衆号：愛寫bug

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

不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。

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

Given an array nums and a value val, remove all instances of that value

in-place

and return the new length.

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

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

示例 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。

注意這五個元素可為任意順序。

你不需要考慮數組中超出新長度後面的元素。           

說明:

為什麼傳回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以“引用”方式傳遞的，這意味着在函數裡修改輸入數組對于調用者是可見的。

你可以想象内部操作如下:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);

// 在函數裡修改輸入數組對于調用者是可見的。
// 根據你的函數傳回的長度, 它會列印出數組中該長度範圍内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}           

解題思路：

​ 隻允許原數組修改，可以用雙指針，左指針 i 自左向右，右指針 j 從右向左。如果索引 i 和 val 相等，則索引 i 得到索引 j 的值，并且 j 前移一位。如果不相等，i 後移一位。

​ 因為要求是傳回修改後的長度并隻考慮該長度的數組，那麼就不用考慮該長度之後的數組，是以隻需得到索引 j 的值，不用再把索引 j 的值改為索引 i的值。

Java：

class Solution {
    public int removeElement(int[] nums, int val) {
        int i=0,j=nums.length-1;//i-左指針；j-右指針
        while (i<=j){
            if(nums[i]==val){
                nums[i]=nums[j];//得到索引j的值，無需把索引j的值改為索引i的值
                j--;
            }else i++;
        }
        return j+1;
    }
}           

Python3：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i=0
        j=len(nums)-1
        while i<=j:
            if(nums[i]==val):
                nums[i]=nums[j]
                j-=1
            else:i+=1
        return j+1           

總結：

​ 這道題本身很簡單，隻要搞清思路，一起都會變得明了。