100. 删除排序数组中的重复数字

描述

中文English

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

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

输入: [1,1,2]

输出: 2 解释: 数字只出现一次的数组为: [1,2]

首先看到这道题的时候，我想把重复的数字之后的数字全部向前一位，然后删除最后一位的数字

代码如下

int delect(vector<int> &a) { int t = 0; for (int i = 0; i < a.size()-1; i++) { for (int j = i+1; j < a.size(); j++) { if (a[i] == a[j]) { t++;//决定向前移动几次 continue; } else { int k = j; while (t>0) { while (k<a.size()) { a[k - 1] = a[k]; k++; } a.pop_back(); t--; } } } } return a.size(); }

下面还有一种方法说直接删除。

int delect1(vector<int> &a) { auto be = a.begin(); for (int i = 1; i < a.size(); i++)// 1 1 1 2 2 5 6 { if (*be == a[i]) { be = a.erase(be); i--;//删除元素后也要让i在be的前一个 } else be++; } return a.size(); }

 

还有一种方法，利用了快慢指针，我们跳过相等的元素，只找所有相等元素中的一个元素，然后放到前面

int delect2(vector<int> &a)//1 1 1 1 2 2 5 6 { if(a.size()==0) return 0; int k=0; for(int i=1;i<a.size();i++) { if(a[k]!=a[i]) { a[++k]=a[i]; } } return k+1; }