# Description

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

You should:

1. Do it in place in the array.
2. Put the element after removing the repetition at the beginning of the array.
3. Return the number of elements after removing duplicate elements.

# Example

Example 1:

Input:
nums = [1,3,1,4,4,2]
Output:
[1,3,4,2,?,?]
4

Explanation:

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.

Example 2:

Input:
nums = [1,2,3]
Output:
[1,2,3]
3

Challenge

1. Do it in O(n) time complexity.
2. Do it in O(nlogn) time without extra space.

# Solution

• O(nlogn), O(1) in space complexity

3. 先 sort Array
4. 用兩個指針，左和右，左指針與右指針相同時，右指針繼續往前，直到左右指針的值不一樣時，左指針往後移一位，且該位置等於右指針的值。

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;

      Arrays.sort(nums);

      int len = 0;

      for (int i = 0; i < nums.length ; i++){

          if (nums[i] != nums[len]){

              len++;

              nums[len] = nums[i];

          }

      }

      return len + 1;

    }

}

• O(n), O(n) space
  用 set

public class Solution {

    /**

     * @param nums: an array of integers

     * @return: the number of unique integers

     */

    public int deduplication(int[] nums) {

       Set<Integer> set = new HashSet<>();

       for (int n: nums){

           set.add(n);

       }

       int res = 0;

       for (Integer n: set){

           nums[res] = n;

           res++; 

       }

       return res;

    }

}