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、第一種實(shí)現(xiàn)方式
思路：遍歷vector的所有項(xiàng)，分別與val比較
- 相同： index不加，nums[i] 賦值給nums[index]
- 不相同：index加1，不需要賦值
2.1 頭文件和準(zhǔn)備工作
#include <iostream>
#include <vector>
using namespace std;
2.2 實(shí)現(xiàn)代碼
/*
思路：遍歷vector的所有項(xiàng)，分別與val比較
相同： index不加，nums[i] 賦值給nums[index]
不相同：index加1，不需要賦值
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度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 測(cè)試代碼
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 運(yùn)行結(jié)果
3、第二種實(shí)現(xiàn)方式
思路：利用remove和distance函數(shù)實(shí)現(xiàn)。
參考來自于：https://github.com/soulmachine/leetcode
remove MSDN介紹
remove 博客參考
distance MSDN介紹
3.1 remove()
3.1.1 語(yǔ)法
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
3.1.2 參數(shù)
-
_First
尋址要?jiǎng)h除元素的范圍中的第一個(gè)元素位置的迭代器。 -
_Last
尋址要?jiǎng)h除元素的范圍中的最后一個(gè)元素的下一個(gè)位置的迭代器。 -
_Val
要從該范圍刪除的值。
3.1.3 返回值
一個(gè)指向最后一個(gè)的下一個(gè)“不刪除的”元素的迭代器。返回值是區(qū)間的“新邏輯終點(diǎn)”。
3.1.4 注意
vector中的remove的作用是將等于value的元素放到vector的尾部，但并不減少vector的size
3.2 distance()
3.2.1 語(yǔ)法
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(
InputIterator _First,
InputIterator _Last
);
3.2.2 參數(shù)
-
_First
要計(jì)算距離迭代器的起點(diǎn)。
_Last
要計(jì)算距離迭代器的終點(diǎn)。
3.2.3 返回值
? _First和_Last之間元素的個(gè)數(shù)。
3.2.3 要求
Header: <iterator>
Namespace: std
3.3 頭文件和準(zhǔn)備工作
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
3.4 實(shí)現(xiàn)代碼
/*
思路：利用distance和remove函數(shù)實(shí)現(xiàn)
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)
*/
class Solution2
{
public:
int removeElement(vector<int>& nums, int val)
{
return distance(nums.begin(), remove(nums.begin(), nums.end(), val));
}
};
3.5 測(cè)試代碼
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 運(yùn)行結(jié)果
4、完整代碼
完整代碼見于GitHub 。
