C++：Leetcode-27移除元素C++：Leetcode-27移除元素题目思路分析总结

66 阅读 0 评论 44 点赞

我是靠谱客的博主知性马里奥，最近开发中收集的这篇文章主要介绍C++：Leetcode-27移除元素C++：Leetcode-27移除元素题目思路分析总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C++：Leetcode-27移除元素

Leetcode27移除元素题，简单题，二分法解法，稍作记录
第二种解法双指针法，重点双指针法！！！
erase()删除函数，时间复杂度为O(n)，不宜使用

文章目录

C++：Leetcode-27移除元素
题目
思路分析
- 1.二分法求解
- 2.双指针法求解
总结

题目

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

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

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

思路分析

1.重点不新增空间
2.不考虑数组中超出新长度的元素
3.元素的顺序可以改变，即最后输出的nums = [0,1,4,0,3]元素顺序无所谓，那就更为降低难度

1.二分法求解

先排序
然后对特殊情况进行判定
然后二分法找val值的左右边界
然后根据边界值返回去掉val值后的长度

/*
代码随想录-数组-Leetcode-27移除元素
题目：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

class Solution
{
private:
    //二分法求右边界
    int getRightBorder(vector<int> nums, int val)
    {
        int left = 0;
        int right = nums.size() - 1;
        int middle;
        while (left <= right)
        {
            middle = left + (right - left) / 2;
            if (nums[middle] > val)
            {
                right = middle - 1;
            }
            else if (nums[middle] < val)
            {
                left = middle + 1;
            }
            else
            {
                left = middle + 1;
            }
        }
        return right;
    }

    //二分法求左边界
    int getLeftBorder(vector<int> nums, int val)
    {
        int left = 0;
        int right = nums.size() - 1;
        int middle;
        while (left <= right)
        {
            middle = left + (right - left) / 2;
            if (nums[middle] > val)
            {
                right = middle - 1;
            }
            else if (nums[middle] < val)
            {
                left = middle + 1;
            }
            else
            {
                right = middle - 1;
            }
        }
        return left;
    }

public:
    Solution(/* args */) {}
    ~Solution() {}
    int removeElement(vector<int> &nums, int val)
    {

        //升序排序
        sort(nums.begin(), nums.end());
        //二分法求右边界值
        int leftBorder = getLeftBorder(nums, val);
        int rightBorder = getRightBorder(nums, val);
        int valNums = rightBorder - leftBorder + 1; //val的个数

        //特殊情况的判断
        if (nums.size() == 0) //nums为空时
        {
            return 0;
        }
        else if (leftBorder < 0 || rightBorder > nums.size() - 1 || rightBorder < leftBorder) //nums内无对应val值时,即不用删除元素，返回原数组长度
        {
            return nums.size();
        }

        //移动元素，覆盖目标值
        int tempNeed = rightBorder + 1; //保留的元素
        int tempDelete = leftBorder;    //删掉的元素。即被覆盖的元素
        while (tempNeed <= nums.size() - 1)
        {
            nums[tempDelete] = nums[tempNeed];
            tempNeed++;
            tempDelete++;
        }
        return nums.size() - valNums;
    }
};

int main(int argc, const char **argv)
{
    vector<int> nums;

    nums.push_back(0);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(0);
    nums.push_back(4);
    nums.push_back(2);

    Solution s1;
    vector<int> res;
    s1.removeElement(nums, 2);
    for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++)
    {
        cout << *it << endl;
    }

    return 0;
}

2.双指针法求解

1.重点理解快指针与慢指针分别代表含义
2.快指针：获取新数组的元素
3.慢指针：作为新数组元素的下标值

快指针移动，当元素值不为删除值时，将快指针值赋值给慢指针，快指针慢指针同时++移动
快指针为要删除值时，快指针接着++移动，去寻找新数组的值；慢指针作为下标值不动
一直循环至数组结束，返回慢指针，因为慢指针最后多了++的操作，所以返回的是下标值+1,即返回的是新数组的个数

/*
leetcode-27移除元素-双指针解法

思路分析：
1.重点理解快指针与慢指针分别代表的含义
2.快指针，获取新的数组元素，即不是目标val值
3.慢指针，作为新的数组元素的下标

*/

#include "iostream"
#include "vector"
using namespace std;

//双指针法
class Solution
{
private:
public:
    Solution(/* args */) {}
    ~Solution() {}
    int removeElement(vector<int> &nums, int val)
    {
        int fastIndex = 0;
        int lowIndex = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            //只有当快指针等于新数组的值时，跟新慢指针
            //当快指针等于要删除的值时，慢指针不更新，快指针接着移动，即接着寻找新数组的值
            if (nums[fastIndex] != val)
            {
                nums[lowIndex] = nums[fastIndex];
                lowIndex++;
            }
            fastIndex++;
        }
        return lowIndex; //返回慢指针，慢指针在最后多了个加一操作，即返回了新数组的个数
    }
};

int main(int argc, const char **argv)
{
    vector<int> nums;

    nums.push_back(0);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(0);
    nums.push_back(4);
    nums.push_back(2);

    Solution s1;
    vector<int> res;
    cout << s1.removeElement(nums, 0) << endl;

    // for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++)
    // {
    //     cout << *it << endl;
    // }
    return 0;
}