编程知识 cdmana.com

How to remove duplicate elements of 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;
    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 :

_____________

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