lint0521 Remove Duplicate Number

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

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.
4. You don't need to keep the original order of the integers.

Example 1:
Input:
nums = [1,3,1,4,4,2]
Output:
[1,3,4,2,?,?]
4
Explanation:
Move duplicate integers to the tail of nums => nums = [1,3,4,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.

Example 2:
Input:
nums = [1,2,3]
Output:
[1,2,3]
3
Challenge
Do it in O(n) time complexity.
Do it in O(nlogn) time without extra space.

• 方法一：以插入排序为基础，把最小的元素插到前面，如果遇到重复的元素nums[j], 则用最后一个元素nums[pos-1]覆盖nums[j],然后pos--关键的一点是：覆盖后，j要减1，也就是nums[j]更新了，需要重新比较
  100% test cases passedTotal runtime 2972 ms
  Your submission beats 83.80% Submissions!

public class Solution {
    public int deduplication(int[] nums) {
        // write your code here
        return insertsort(nums);
    }
    private int insertsort(int[] nums) {
        int pos=nums.length;
        int i,j,idx,tmp;
        for(i=0;i<pos-1;++i){
            idx=i;
            for(j=i+1;j<pos;++j){
                if(nums[idx]>nums[j])
                    idx=j;
                else if(nums[idx]==nums[j]){
                    nums[j]=nums[pos-1];
                    pos--;
                    j--;//回退，nums[pos-1]的值要重新判断
                }
            }
            if(i!=idx){
                tmp=nums[i];
                nums[i]=nums[idx];
                nums[idx]=tmp;
            }
        }
        return pos;
    }
}

方法二：利用HashMap,运行速度不如插入排序，比较奇怪
100% test cases passedTotal runtime 2977 ms
Your submission beats 80.40% Submissions!

// O(n) time, O(n) space
public class Solution {
    public int deduplication(int[] nums) {
        // Write your code here
        HashMap<Integer, Boolean> mp = new HashMap<Integer, Boolean>();
        for (int i = 0; i < nums.length; ++i)
            mp.put(nums[i], true);

        int result = 0;
        for (Map.Entry<Integer, Boolean> entry : mp.entrySet())
            nums[result++] = entry.getKey();
        return result;
    }
}

方法三 Java的函数Array.sort是利用双轴快速排序，可是速度却是三个里面最慢的这是什么原因呢？
100% test cases passedTotal runtime 3027 ms
Your submission beats 58.40% Submissions!

// O(nlogn) time, O(1) extra space
public class Solution {
    public int deduplication(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        Arrays.sort(nums);
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[len]) {
                nums[++len] = nums[i];
            }
        }
        return len + 1;
    }
}

方法四 HashSet 网友提供，未深入研究

// o(n) time, o(n) space
public class Solution {
    public int deduplication(int[] nums) {
        if (nums == null || nums.length == 0) {
        return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            }
        }
        int index = 0;
        Iterator it = set.iterator();
        while (it.hasNext()) {
            nums[index++] = (int) it.next();
        }
        return index;
    }
}