[leetcode_26] Remove Duplicates from Sorted Array

Remove duplicate elements from a sorted array without allocating extra space.

Use insertion sort-style swapping to move duplicates to the end of the array. Somewhat similar to the previous problem.

Accepted on the first try. Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int count = 0;
        int now = A[0];
        for(int i = 1; i < n-count; i++) {
            if(now == A[i]) {
                for(int j = i+1; j < n-count; j++) {
                    int tmp = A[j];
                    A[j] = A[j-1];
                    A[j-1] = tmp;
                }
                count++;
                i--;
            } else {
                now = A[i];
            }
        }
        return n - count;
    }
};