## How to remove duplicate elements of ordered array

remove duplicate elements ordered array

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 for the general algorithm to deal with arrays , We should only operate on the elements at the end of the array as much as possible , To avoid the extra time complexity .

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

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). And the title requires us to revise it in place , In other words, auxiliary arrays can't be used , Space complexity has to be O(1).

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 .

Actually , For array related algorithms , There's a general technique ： Try to avoid deleting elements in the middle , Then I'll try to change this element to the last . In this case , Finally, the elements to be deleted are dragged at the end of the array , One by one pop Just drop it , The time complexity of each operation is reduced to O(1) 了 .

According to this idea , It can also derive a common way to solve similar requirements ： Double pointer technique . To be specific , It should be a slow and fast pointer .

Let's slow the pointer `slow` Go back to the left , 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 , All the elements after that are repeating elements .

``````int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int slow = 0, fast = 1;
while (fast < n) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain nums[0..slow] No repetition
nums[slow] = nums[fast];
}
fast++;
}
// The length is the 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 ？ Actually as like as two peas , 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;