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限佩、第一種實現(xiàn)方式
思路：遍歷vector的所有項葵诈，分別與val比較
- 相同： index不加，nums[i] 賦值給nums[index]
- 不相同：index加1祟同，不需要賦值
2.1 頭文件和準備工作
#include <iostream>
#include <vector>
using namespace std;
2.2 實現(xiàn)代碼
/*
思路：遍歷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 運行結果
3窖贤、第二種實現(xiàn)方式
思路：利用remove和distance函數(shù)實現(xiàn)砖顷。
參考來自于：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 參數(shù)
-
_First
尋址要刪除元素的范圍中的第一個元素位置的迭代器赃梧。 -
_Last
尋址要刪除元素的范圍中的最后一個元素的下一個位置的迭代器滤蝠。 -
_Val
要從該范圍刪除的值。
3.1.3 返回值
一個指向最后一個的下一個“不刪除的”元素的迭代器授嘀。返回值是區(qū)間的“新邏輯終點”物咳。
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 參數(shù)
-
_First
要計算距離迭代器的起點蹄皱。
_Last
要計算距離迭代器的終點览闰。
3.2.3 返回值
? _First和_Last之間元素的個數(shù)芯肤。
3.2.3 要求
Header: <iterator>
Namespace: std
3.3 頭文件和準備工作
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
3.4 實現(xiàn)代碼
/*
思路：利用distance和remove函數(shù)實現(xiàn)
時間復雜度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 運行結果
4压鉴、完整代碼
完整代碼見于GitHub 崖咨。
