Lintcode - Remove Duplicate Numbers in Array

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.

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.

Analysis:

For the first challege, do it in O(n) time complexity. It's straightforward. One can simply use two pointers, from the begining of the array and the other from the tail. for each number, put it in the hashset. If it's already in the hashset. Switch it with the number pointed by the second pointer until the left point and the right point crossed.

public int deduplication(int[] nums) {
        int right = nums.length - 1;
        HashSet<Integer> set = new HashSet<Integer>();

        for (int i = 0; i <= right; i++){
            while (set.contains(nums[i])){
                if (i == right){
                    right--;
                    break;
                }
                switchNum(nums, i, right);
                right--;
            }

            set.add(nums[i]);
        }

        return right + 1;
    }

    public void switchNum(int[] nums, int p1, int p2){
        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }

For the second challenge, do it in O(nLogn) without extra space. This is a little tricky. It means that we cannot use HashSet to check whether there is a duplicates or not. O(nlogn) time complexity indicates that there must a sorting involved. After sorting the numbers, we can still use two pointers to move the numbers. The first pointer is pointing to the unique occurrence and the second pointer is used to loop over the numbers.

    public int deduplication(int[] nums) {
        if (nums.length == 0){
            return 0;
        }
        Arrays.sort(nums);        
        int j = 0;        
        for (int i = 0; i < nums.length; i++){
            if (nums[j] != nums[i]){
                nums[++j] = nums[i];
            }
        }

        return j + 1;
    }