> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/7.two-pointers/521remove-duplicate-numbers-in-array.md).

# 521.Remove Duplicate Numbers in Array

## 1.Description(Medium)

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

You should:\
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.

### Notice

You don't need to keep the original order of the integers.

**Example**

Given*nums*=`[1,3,1,4,4,2]`, you should:

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.

[**Challenge**](https://www.lintcode.com/en/problem/remove-duplicate-numbers-in-array/#challenge)

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

## 2.Code

Solution 1：HashSet ，O(n) time, O(n) space

```
//Solution 1: O(n) time, O(n) space
    public int deduplication(int[] nums) {
        //HashMap<Integer,Boolean> map=new HashMap<Integer,Boolean>();
        HashSet<Integer> set=new HashSet<Integer>();
        for(int i=0;i<nums.length;i++){
            if(!set.contains(nums[i])){
                set.add(nums[i]);
            }
        }
        int result=0;
        for(Integer element:set){
            nums[result]=element;
            result++;
        }
        return result;
    }
```

Solution 2：In place O(nlogn) time, O(1) extra space

<http://www.jiuzhang.com/solutions/remove-duplicate-numbers-in-array/>

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

**这个题目分array有没有sorted.**

1.如果已经是sorted的话，最好的方法是就是用一个prev记录前面的，然后遍历，直接加进result,不必要浪费O(n) 的space 去建立一个hashset.

2.如果没有sorted,就是这个题，第一种是时间花费O(n)，空间花费O(n)建一个hashset.

```
                                                  第二种是
```