Given an array of integers, remove the duplicate numbers in it.

You should:

1. Do it in place in the array.
2. Move the unique numbers to the front of the array.
3. Return the total number of the unique numbers.

Notice

You don't need to keep the original order of the integers.

Have you met this question in a real interview?

Yes

Example

Givennums=[1,3,1,4,4,2], you should:

1. Move duplicate integers to the tail of nums = > nums = [1,3,4,2,?,?] .
2. Return the number of unique integers in nums = > 4 .

Actually we don't care about what you place in?, we only care about the part which has no duplicate integers.

Challenge

1. Do it in O(n) time complexity.
2. Do it in O(nlogn) time without extra space.

class Solution {
public:
    /**
     * @param nums an array of integers
     * @return the number of unique integers
     */
    int deduplication(vector<int>& nums) {
        // Write your code here
        if (nums.empty()) {
            return 0;
        }
        sort(nums.begin(), nums.end());
        int index = 0;
        for (int num : nums) {
            if (num != nums[index]) {
                nums[++index] = num;   
            }
        }
        return index + 1;
    }
};