编程知识 cdmana.com

How to remove duplicate elements of ordered array

After reading this article , You can go and get 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 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;
    ListNode slow = head, fast = head.next;
    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;
}

_____________

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 !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢

Scroll to Top