LintCode 521 Remove Duplicate Numbers in Array

思路1

HashSet记录不重复数字，然后从数组开头开始替换成hashset中的元素。

时间复杂度O(n)
空间复杂度O(n)

代码1

public class Solution {
    /*** @param nums an array of integers* @return the number of unique integers*/public int deduplication(int[] nums) {
    // Write your code hereHashMap<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

使用hashset记录不重复的数字，然后设置两个同向指针，快指针遍历数组，慢指针始终指向下一个替换位置，遇到set里没有的元素：加入set；将i指向的元素替换到index处；同时说明此处不是替换位置，于是index应该后移。
这样的好处是可以保持原来元素的相对位置。

时间复杂度O(n)
空间复杂度O(n)

代码2

public class Solution {
    /*** @param nums: an array of integers* @return: the number of unique integers*/public int deduplication(int[] nums) {
    // write your code hereHashSet<Integer> set = new HashSet<>();int index = 0;for (int i = 0; i < nums.length; i++) {
    if (!set.contains(nums[i])) {
    set.add(nums[i]);nums[index] = nums[i];index++;}}return set.size();}
}

思路3

排序+同向双指针。首先将数组排序，这样重复的元素就会排在一起。然后利用同向双指针，一个指针i走得快，遍历整个数组；另一个指针index始终指向上一个不重复元素，这样index+1的位置就是下一个插入的位置，遇到与i指向元素不同的，index++然后将i的元素赋给index指向的元素。

时间复杂度O(nlogn)
空间复杂度O(1)

代码3

public class Solution {
    /*** @param nums: an array of integers* @return: the number of unique integers*/public int deduplication(int[] nums) {
    // write your code hereif (nums == null || nums.length == 0) {
    return 0;}Arrays.sort(nums);int index = 0;for (int i = 0; i < nums.length; i++) {
    if (nums[i] != nums[index]) {
    index++;nums[index] = nums[i];}}return index + 1;}
}