Array系列之Remove Element

1、要求

Given an array and a value, remove all instances of that > value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.

2、第一种实现方式

思路：遍历vector的所有项，分别与val比较

• 相同： index不加，nums[i] 赋值给nums[index]
• 不相同：index加1，不需要赋值

2.1 头文件和准备工作

#include <iostream>
#include <vector>
using namespace std;

2.2 实现代码

/*
    思路：遍历vector的所有项，分别与val比较
        相同： index不加，nums[i] 赋值给nums[index]
        不相同：index加1，不需要赋值
    时间复杂度O(n)，空间复杂度O(1)
*/
class Solution
{
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int index = 0;
        for (size_t i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != val)
                nums[index++] = nums[i];
        }

        return index;
    }   
};

2.3 测试代码

int main()
{
    using namespace std;
    Solution sol;
    vector<int> vec{1, 2, 5, 6, 12, 45, 8, 4, 5, 4};
    cout << "Original vector's size is " << vec.size() << endl;

    int count = sol.removeElement(vec, 5);

    cout << "New vector's size is " << count << endl;
    for (int i = 0; i < count; ++i)
        cout << "vec[" << i << "] = " << vec[i] << endl;

    return 0;
}

2.4 运行结果

result1

3、第二种实现方式

思路：利用remove和distance函数实现。
参考来自于：https://github.com/soulmachine/leetcode
remove MSDN介绍
remove 博客参考
distance MSDN介绍

3.1 remove()

3.1.1 语法

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
    const T& value);

3.1.2 参数

• _First
  寻址要删除元素的范围中的第一个元素位置的迭代器。
• _Last
  寻址要删除元素的范围中的最后一个元素的下一个位置的迭代器。
• _Val
  要从该范围删除的值。

3.1.3 返回值

一个指向最后一个的下一个“不删除的”元素的迭代器。返回值是区间的“新逻辑终点”。

3.1.4 注意

vector中的remove的作用是将等于value的元素放到vector的尾部，但并不减少vector的size

3.2 distance()

3.2.1 语法

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
   distance(
      InputIterator _First, 
      InputIterator _Last
   );

3.2.2 参数

• _First

  要计算距离迭代器的起点。

• _Last
  要计算距离迭代器的终点。

3.2.3 返回值

​ _First和_Last之间元素的个数。

3.2.3 要求

Header: <iterator>
Namespace: std

3.3 头文件和准备工作

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

3.4 实现代码

/*
    思路：利用distance和remove函数实现
    时间复杂度O(n)，空间复杂度O(1)
*/
class Solution2
{
public:
    int removeElement(vector<int>& nums, int val) 
    {
        return distance(nums.begin(), remove(nums.begin(), nums.end(), val));
    }
};

3.5 测试代码

vector<int> vec2{3,2,2,3};
int count = sol2.removeElement(vec2, 3);
cout << "New vector2's size is " << count << endl;
cout << "New vector2's real size is " << vec2.size();
for (int i = 0; i < count; ++i)
  cout << "vec[" << i << "] = " << vec2[i] << endl;

3.6 运行结果

result2

4、完整代码

完整代码见于GitHub 。