删除有序数组中的重复项

描述:

给你一个升序排列的数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度。元素的相对顺序应该保持一致 。

示例:

1
2
3
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

代码1:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int index = 1;
for(int i=1;i<nums.size();++i) {
if(nums[i] != nums[index-1]) {
nums[index++] = nums[i];
}
}
return index;
}
};

代码2:

1
2
3
4
5
class Solution {
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(),unique(nums.begin(),nums.end()));
}
};
1
2
3
4
5
6
7
//distance()函数用于计算两个迭代器表示的范围内包含元素的个数
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);
/*
1. 其中,first 和 last 都为迭代器,其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器
2. 该函数会返回[first, last)范围内包含的元素的个数。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
<algorithm>中的unique函数,它能删除连续序列的副本(Remove consecutive duplicates in range). 原型如下:
*/
template <class ForwardIterator>
ForwardIterator unique ( ForwardIterator first, ForwardIterator last );

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique ( ForwardIterator first, ForwardIterator last,
BinaryPredicate pred );
/*
“删除连续序列”这样的描述容易造成误解,知道下面几点有助于更好理解这个操作:
1. 其实unique仅仅是按照一个规则来修改[first, last)之间的元素,并不会删除任何东西,它不会改变容器的size。这个规则就是连续一样的元素会被后面的元素覆盖。
2. 它通过一个返回迭代器result,并保证在[first, result)之间的元素是不存在连续重复的元素。可以把[result, last)之间的元素移除掉,这才算删除了连续重复的元素。
3. 默认判断两个元素相等是使用==操作符,第二个版本也可自己指定二元函数(函数,functors,lambda…).
*/

删除有序数组中的重复项 II

描述:

给你一个有序数组 nums ,请你原地删除重复出现的元素,使每个元素最多出现两次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

示例:

1
2
3
输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

代码1:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 2) return nums.size();
int index = 2;
for (int i = 2; i < nums.size(); i++) {
if (nums[i] != nums[index - 2])
nums[index++] = nums[i];
}
return index;
}
};