[关闭]
@kuailezhishang 2014-12-10T20:08:42.000000Z 字数 618 阅读 2145

Remove Duplicates from Sorted Array II

Leetcode


题目:

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

给定一个有序表,每个元素最多出现两次。删除掉多余的元素,返回剩余元素的个数。

思路:

两个指针,一个指向合法位置的下一个位置 (index) ,另一个用于遍历元素 (i) 。两个指针之间的是无效元素。

这个时候判断 i 指向的元素和 index - 2 指向的元素是否相同。

代码如下:

  1. class Solution {
  2. public:
  3. int removeDuplicates(int A[], int n) {
  4. int deleted = 0; //已经删除的元素个数
  5. if(n < 3) //最多含有2个元素,一定满足题意
  6. return n;
  7. int index = 2; //可能不合法的位置
  8. for(int i = 2; i < n; i++)
  9. {
  10. if(A[i] != A[index - 2] )
  11. A[index++] = A[i];
  12. }
  13. return index;
  14. }
  15. };
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注