27. 移除元素

27. 移除元素

https://leetcode.cn/problems/remove-element/description/

方法一：

将后面所有不等于val的元素向前赋值移动

弊端：大量不等于val的元素会被重复赋值

class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for (int num : nums) {
            if(num != val){
                nums[idx++] = num;
            }
        }
        return idx;
    }
}

方法二：双指针

左右两个指针分别向中间移动

如果左指针指向的元素是val，则将右指针指向的元素覆盖左边的元素，同时当前右指针指向的元素就不可用了，所以右指针向左移动一位

如果左指针指向的元素不是val，则保留这个元素，左指针向右移动

注意的是：最后边界条件的判断，最后左右指针必须重合指向同一个元素，才能保证长度计算正确

public class Solution2 {
    public int removeElement(int[] nums, int val) {
        // while里是<，则这里 right 必须为 nums.length：
        // left和right才能指向同一个位置进行最后一个元素的判断
        int left = 0, right = nums.length;
        while(left < right){
            if(nums[left] == val){
                nums[left] = nums[--right];
            }else{
                ++left;
            }
        }
        return right;
    }


    public int removeElement2(int[] nums, int val) {
        // while里是<=，则这里 right 必须为 nums.length-1：
        // left和right才能指向同一个位置进行最后一个元素的判断
        int left = 0, right = nums.length-1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right--];
            }else{
                ++left;
            }
        }
        return right+1;
    }
}

我的解法：

不同在于，我的解法进一步减少了数据的复制次数，对于右指针指向的等于val的元素并不会复制给左指针，而是跳过，指导找到一个不等于val的元素

class Solution {
    public int removeElement(int[] nums, int val) {
        int begin = 0, end = nums.length-1;
        while(begin < end){
            while(begin < end && nums[begin] != val) ++begin;
            while(end >= 0 && nums[end] == val ) --end;
            if(begin>= end) break;
            int temp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = temp;
        }
        if(end == 0 && nums[end] == val) {
            return 0;
        }
        return end+1;
    }
}