力扣题目链接

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路

双指针（初始版本）

定义两个指针，i和j，开始时都指向数组下标为0的位置。j指针不停遍历，直到最后一个元素停止；每轮遍历，判断i指针指向的数组元素是否与val相等，若不相等，i指针直接后移一位；若相等且j指针指向的数组元素与val不相等，则交换。交换的原因是判断条件是看i指向的值是否与val相等，j在i的前面，同样的元素判断两次会出错，不能直接赋值。很天真的使用位运算来交换两个值，以为能快点，其实也差不多。

int removeElement(int* nums, int numsSize, int val){
    
    int i = 0, j = 0;

    while (j < numsSize) {

        if (nums[i] != val) {
            i++;
        } else if (nums[i] == val && nums[j] != val) {
            nums[i] = nums[i] ^ nums[j];
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
            i++;
        }

        j++;
    }

    return i;
}

双指针（改进版本）

上面的解法太绕了，如果判断条件是看j指向的值是否与val相等，就不会一个元素判断两次，直接赋值即可。

int removeElement(int* nums, int numsSize, int val){
    int i = 0, j = 0;

    while (j < numsSize) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }

        j++;
    }

    return i;
}

总结

  1. 需要注意判断条件，需要规避重复处理的情况
  2. 注意设置双指针的时候不同指针的方向和速度要
最后修改：2024 年 11 月 05 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏