【LeetCode27】移除元素（双指针）1.题目2.思路3.代码

83 阅读 0 评论 55 点赞

我是靠谱客的博主神勇店员，这篇文章主要介绍【LeetCode27】移除元素（双指针）1.题目2.思路3.代码，现在分享给大家，希望可以做个参考。

1.题目

2.思路

要原地去掉数值为val的数，最浅显的暴力做法就是遍历到该数时直接依次将数组后面的数字往前移动一个，如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

但是力扣上会超时，链表和数组题我们经常使用双指针，这题可以设置快慢指针——只for遍历一次，快指针i冲在前，而如果遇到目标val值时，慢指针j就歇一格，并且将快指针i所在的元素复制到慢指针j所在的位置上；
而当没有遇到目标val值就i和j同并进。
在这里插入图片描述

3.代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size=nums.size();
        int j=0;//慢指针
        for(int i=0;i<size;i++){//i为快指针
            if(nums[i]!=val){
                nums[j++]=nums[i];
            }
        }
        return j;
    }
};