Remove-Duplicate-Numbers-in-Array.md

##Remove Duplicate Numbers in Array Given an array of integers, remove the duplicate numbers in it.

You should:

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

###Example Given nums = [1,3,1,4,4,2], you should:

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.

###Challenge Do it in O(n) time complexity. Do it in O(nlogn) time without extra space. Notice You don't need to keep the original order of the integers.

###思路1

• 解决O(n) time complexity
• 使用一个map就行

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

###思路2

• 先排序
• 再两根指针，需要着重掌握
• 由于根本不管后面的重复元素放不放在后面，只需要保证unique的元素放在前面就行
• 一根指针向右走找相同的元素，一根指针就指向当前该写的元素
• 自己写的时候把很简单的问题写得却很复杂

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