[LeetCode]80.Remove Duplicates from Sorted Array II

【题目】

Remove Duplicates from Sorted Array II

Total Accepted:4460Total Submissions:15040My Submissions

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

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;
}