1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*
代码随想录-数组-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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
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;
}