山楼小院在哪家网站做宣传/外贸怎么建立自己的网站

原题网址：http://www.lintcode.com/zh-cn/problem/remove-duplicates-from-sorted-array/#

给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。

不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。

标签 

两根指针 数组 脸书 Bloomberg 微软

思路1：

最开始的想法是for循环遍历，循环变量i从size-1开始，当i大于0时：

如果当前元素与前一个元素相等，当前元素之后的元素整体左移一个索引，全部左移完成后，删除最后一个元素；

如果不相等，i--。

程序在VS2010上可以通过，但放到lintcode上现实超时……好吧，换一个思路。

思路2：

还是for循环遍历，但循环体内再加一个while循环，找到与当前元素相等的所有元素并记录下标范围，然后一起删除，这次AC了，代码如下：

注意：vec.erase(vec.begin()+i,vec.begin()+j); 删除区间[i,j-1]，区间从0开始，i，j为数组下标。

也就是说如果想删除区间[i，j]应写成vec.erase(vec.begin()+i,vec.begin()+j+1);

class Solution {
public:/** @param nums: An ineger array* @return: An integer*/int removeDuplicates(vector<int> &nums) {// write your code hereint i=0;for (;i<(int)nums.size()-1;i++){int s=i;while(i<(int)nums.size()-1&&nums[i]==nums[i+1]){i++;}if (i>s){nums.erase(nums.begin()+s+1,nums.begin()+i+1);}i=s;}return (int)nums.size();}
};

参考：vector::erase() vector中如何删除元素？

思路3：

在网上查了查，果然能发现更好的方法，学无止境……

参考  https://blog.csdn.net/fly_yr/article/details/51548657

https://www.cnblogs.com/libaoquan/p/7157733.html

如何使用vector的reserve和resize方法

C++：vector中的resize()函数 VS reserve()函数

感觉有点类似于插入排序，将数组分为两段，前一段是已经删除重复元素的数组，后一段是未删除重复元素的数组；
用下标 i 指向非重数组最大值（即数组最右边的元素），下标 j 指向重复数组中第一个与非重数组中元素不同的元素；
将 j 指向的元素值赋给 i+1 指向的元素，即可增大非重数组；

AC代码：

class Solution {
public:/** @param nums: An ineger array* @return: An integer*/int removeDuplicates(vector<int> &nums) {// write your code hereint size=nums.size();if (size==0){return 0;}int i=0,j=1;while(j<size){if (nums[j]!=nums[i]){nums[i+1]=nums[j];i++;j++;}else{j++;}}nums.resize(i+1);return i+1;}
};