27-移除元素

LeetCode 27. Remove Element

LeetCode-27

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.

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.

method 1: 反向双指针

双指针，前指针找等于val的数，后指针找不等于val的数，然后交换。

注意：这种方法会改变元素的相对位置

int removeElement(vector<int>& nums, int val) {
    if (nums.empty()) return 0;
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        while (l < r && nums[l] != val) l++;
        while (l < r && nums[r] == val) r--;
        swap(nums, l, r);
    }
    return (nums[l] == val ? l : l + 1);
}

method 2: 同向双指针

不改变相对位置

• 如果右指针不等于val，就把右指针的值赋给左指针，同时移动一格
• 如果右指针等于val，右指针移动，左指针不动

时间复杂度：$O(n)$
空间复杂度：$O(1)$

int removeElement(vector<int>& nums, int val) {
    int index = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != val) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

---

LeetCode 283. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

method

用同向双指针的方法，先把非零元素移到前面，再把后面的元素置0

void moveZeroes(vector<int>& nums) {
    int index = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) 
            nums[index++] = nums[i];
    }
    for (; index < nums.size(); index++) {
        nums[index] = 0;
    }
}