描述

给一个整数数组，去除重复的元素。
你应该做这些事：
1.在原数组上操作
2.将去除重复之后的元素放在数组的开头
3.返回去除重复元素之后的元素个数

注意事项

不需要保持原数组的顺序

样例

给出 nums = [1,3,1,4,4,2],你需要做以下操作
1.将重复元素扔在最后面 => nums = [1,3,4,2,?,?].
2.返回个数 4
实际上我们并不在意?是什么

挑战

1.O(n)时间复杂度.
2.O(nlogn)时间复杂度但没有额外空间

知识点

Map 的 entrySet() 方法返回一个实现 Map.Entry 接口的对象集合。集合中每个对象都是底层 Map 中一个特定的键/值对，HashSet 不提供索引取值

代码

1. 用 HashSet 直接去重了，O(n) time, O(n) space

public class Solution {
    /**
     * @param nums an array of integers
     * @return the number of unique integers
     */
    public int deduplication(int[] nums) {
        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()) {
            // map.entrySet 直接返回不重复的键值对，
            // 可通过 entry.getValue 和 entry.getKey 来得到值
            nums[result++] = entry.getKey();
        }
        // nums[results] 在赋完值 results 又自动加了 1，所以结果无需加一
        return result;
    }
}

2. 同向型指针的做法 O(nlogn) time，O(1) extra space

public class Solution {
    /*
     * @param nums: an array of integers
     * @return: the number of unique integers
     */
    public int deduplication(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Array.sort(nums);

        // len 用于记录不重复的最后一个元素的下标
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[len]) {
                // 注意首先已经数组从小到大排好序了
                // 此处是 ++len，先向前移一位再进行赋值
                nums[++len] = nums[i];
            }
        }
        return len + 1;
    }
}