LeetCode

暴力解法

int removeElement(int* nums, int numsSize, int val){
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == val) {
            for (int j = i; j < numsSize - 1; j++){
                nums[j] = nums[j + 1];
            }
            i--;
            numsSize--;
        }
    }
    return numsSize;

}

双指针法：两个指针都从最左边开始遍历

int removeElement(int* nums, int numsSize, int val){
    int left = 0;
    for (int right = 0; right < numsSize; right++) {        
        if (nums[right] != val) {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
}

双指针优化：两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。为了避免如果要移除的元素恰好在数组的开头，我们需要把每一个元素都左移一位这样的麻烦情况。

错误代码：

int removeElement(int* nums, int numsSize, int val){
    int left = 0, right = numsSize - 1;
    while (left <= right){
        if (nums[left] == val) {
            while (nums[right] == val) right--;
            nums[left] = nums[right];
            right--;            
        }
        left++;
    }
    return left;
}

1. 试图去考虑如果从右边赋值过来的值仍等于val的情况，但是我这个方法的思想是错的，无法解决这个问题，答案一定是错的，因为筛选后的right可能导致右边可用的替换值数目不够，不足以用来替换掉左边等于val的数。因此应该让右边的挨个都来替换，替换之后再重新判断是否等于val。
2. while (left <= right) 会出现执行错误，因为如果数组是[1]，val也是1，right变成-1，越界。
3. while (left < right) 会出现解答错误，因为会少去判断和输出最中间 left == right 时的数。
   以上不可调和的矛盾说明：这个思想不可行！

正确代码1：

int removeElement(int* nums, int numsSize, int val){
    int left = 0, right = numsSize;
    while (left < right){
        if (nums[left] == val) {
            nums[left] = nums[right-1];
            right--;            
        } else  left++;
    }
    return left;
}

巧妙之处：这里考虑到了如果从右边赋值过来的值仍等于val的情况，因为赋值后没有 left++;所以还会再继续判断一遍 if (nums[left] == val)，不等于了才会 left++。

正确代码2：

int removeElement(int* nums, int numsSize, int val){
    int left = 0, right = numsSize - 1;
    while (left <= right){
        if (nums[left] == val) {
            nums[left] = nums[right];
            right--;            
        } else  left++;
    }
    return left;
}

这一题学会了双指针的思想