hazel'blog
0%

代码随想录第二天

发表于 更新于 分类于
本文字数： 665 阅读时长 ≈ 1 分钟

数组-移除元素

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
int removeElement(int* nums, int numsSize, int val){
    for(int i = 0; i < numsSize; i++){
        if(nums[i] == val){
            for(int j = i + 1; j < numsSize;j++){
                nums[j-1] = nums[j];
            }
            i--;
            numsSize--;
        }

    }
    return numsSize;
}

这样的党法有一点笨拙，复杂度太高(O(n^2))，看了一下题解的双指针方法：通过一个右指针和左指针在一个For循环下完成两个for循环的工作

右指针 right 指向当前将要处理的元素，左指针left 指向下一个将要赋值的位置。

  • 如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

  • 如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。

1
2
3
4
5
6
7
8
9
10
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;
}