## How to remove duplicate elements of ordered array

remove duplicate elements ordered array

# 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

27. Remove elements

283. Move zero

-----------

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

### 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
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 ：

＿＿＿＿＿＿＿＿＿＿＿＿＿

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 ！