LeetCode刷題: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比較

2.1 頭文件和準備工作

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

2.2 實現代碼

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 運行結果

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 參數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 實現代碼

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 運行結果

4、完整代碼

完整代碼見於GitHub 。