# How to remove duplicate elements from ordered arrays

After reading this article , You've not only learned the algorithmic routine , You can also drop in LeetCode Take the following questions ：

26. Delete duplicates in sort array

83. Delete duplicate elements from the sort list

**-----------**

We know that for arrays , Insert at tail 、 It is more efficient to delete elements , The time complexity is O(1), But if you insert it in the middle or at the beginning 、 Remove elements , It's about moving data , The time complexity is O(N), Low efficiency .

So the last article O(1) Time deletion / Find any element in the array I just talked about a technique , Exchange the element to be deleted to the last one , And then delete it , You can avoid data movement .

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### Ordered array / The chain watch is weightless

Let's talk about how to de duplicate an ordered array , Let's look at the title first ：

The function signature is as follows ：

```
int removeDuplicates(int[] nums);
```

obviously , Because the array has been sorted , So the repeating elements must be connected , It's not hard to find them , But if every duplicate element is found, delete it immediately , Is to delete in the middle of the array , The whole time complexity is going to be O(N^2).

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

Briefly explain what it means to modify in place ：

If it wasn't revised in place , We directly new One `int[]`

Array , Put the de duplicated elements into the new array , Then return the new array .

But delete it in place , We are not allowed to new New array , You can only operate on the original array , And then return a length , In this way, we can get the returned length and the original array to find out what elements we have after de duplication .

This requirement is very common in array related algorithmic problems ,** The general solution is what we mentioned earlier Double pointer technique The fast and slow pointer technique in **.

Let's slow the pointer `slow`

Walk in the back , Quick pointer `fast`

Go ahead and find the way , Find an element that doesn't repeat and tell `slow`

And let `slow`

Take a step forward . So when `fast`

Pointer traverses the entire array `nums`

after ,** nums[0..slow] It's not repeating elements **.

```
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain nums[0..slow] No repetition
nums[slow] = nums[fast];
}
fast++;
}
// The length of the array is index + 1
return slow + 1;
}
```

Take a look at the process of algorithm execution ：

Just expand it a little bit , If I give you an ordered list , How to remove heavy ？ It's a force lock 83 topic , In fact, as like as two peas, the weight is exactly the same , The only difference is that it turns an array assignment into an operation pointer ：

```
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// Disconnect from the following repeating elements
slow.next = null;
return head;
}
```

### Remove elements

It's a force lock 27 topic , Look at the title ：

The function signature is as follows ：

```
int removeElement(int[] nums, int val);
```

The title asks us to put `nums`

All values in are `val`

Delete the element in place , Still need to use Double pointer technique The speed pointer in ：

If `fast`

Encounter elements that need to be removed , Then skip directly , Or tell `slow`

The pointer , And let `slow`

Take a step forward .

This is exactly the same as the solution to the array de duplication problem mentioned earlier , Don't draw GIF 了 , Look directly at the code ：

```
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
```

** Note that there is an important difference between this method and the solution of ordered array de duplication **, We are here to give `nums[slow]`

Assign a value and then give it to `slow++`

, This ensures `nums[0..slow-1]`

Does not contain a value of `val`

The elements of the , The final result is the length of the array `slow`

.

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### Move zero

It's a force lock 283 topic , Let me describe the topic ：

I'll give you an array `nums`

, Would you please ** Modify in place **, Set all values in the array as 0 To the end of the array , The function signature is as follows ：

```
void moveZeroes(int[] nums);
```

For example, I'll give you input `nums = [0,1,4,0,2]`

, Your algorithm has no return value , But I will `nums`

Change the array in place to `[1,4,2,0,0]`

.

A couple of previous topics , Do you have the answer ？

Let's put all of them together 0 Move to the last , It's like removing `nums`

All in 0, Then assign the following elements to 0 that will do .

So we can reuse the previous question `removeElement`

function ：

```
void moveZeroes(int[] nums) {
// Remove nums All in 0
// Return to remove 0 The length of the array after
int p = removeElement(nums, 0);
// take p All subsequent elements are assigned the value of 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// See code implementation above
int removeElement(int[] nums, int val);
```

thus , The four way 「 Modify in place 」 And that's all , In fact, the core is still fast and slow pointer skills , Have you learned ？

Related to recommend ：

- Classic dynamic planning ：0-1 knapsack problem
- Hand to hand brush the binary tree （ The third phase ）

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！