【题目】
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]
.
【代码】
/********************************* * 日期:2014-01-15 * 作者:SJF0115 * 题目: 80.Remove Duplicates from Sorted Array II * 来源:http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ * 结果:AC * 来源:LeetCode * 总结: **********************************/ #include <iostream> #include <stdio.h> using namespace std; // 时间复杂度 O(n),空间复杂度 O(1) class Solution { public: //A数组的重要特点是已经排序 int removeDuplicates(int A[], int n) { if(n == 0){ return 0; } else if(n == 1){ return 1; } //新数组下标 int index = 2; for(int i = 2;i < n;i++){ if(A[i] != A[index-2]){ A[index++] = A[i]; } } return index; } }; int main() { int result; Solution solution; int A[] = {1,1,2,2,2,2,4,4,5,6,8,8,8}; result = solution.removeDuplicates(A,13); printf("Length:%d\n",result); for(int i = 0;i < result;i++){ printf("%d ",A[i]); } return 0; }