Leetcode daily practice - 26. Delete duplicates in an ordered array

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 26. Remove duplicate items from an ordered array

Let’s get it！

---

---

1. Topic analysis

To give you one Ascending order Array of nums , Would you please In situ Delete duplicate elements , Make each element Only once , Returns the new length of the deleted array . Elemental Relative order It should be maintained Agreement .
 
Don't use extra space , You must be there. In situ Modify input array And using $O(1)$ Complete with extra space .
 
In fact, the root of this problem is duplicate removal , Delete the duplicate elements in the array , Keep only one

Example 1：

Example 2：

2. Title diagram

First of all, this question can be used Double pointer Law ;
 
First , Give Way src Pointing elements , And src-1 （ That is to say src The previous element of ） Compare the elements pointed to , If src The element pointed to is related to src-1 The elements pointed to are equal , that src Just move one bit backwards ;
 
If it's not equal , Then put src-1 The element pointed to is assigned to dst In the right place , then src and dst At the same time, move one bit backward .
 
It may sound a little circuitous ？ Don't panic. , Follow the picture step by step ！

But a little different is , The pointer src Point to the subscript 1 The location of , The pointer dst Or point to the starting position , As shown in the figure

In limine src Point to the element and src-1 The elements pointed to are 0, in other words src And src-1 The elements pointed to are equal , As shown in the figure

Then put src Move one back ,dst unchanged , As shown in the figure

here src The element that points to is 1,src-1 The element that points to is 0, Their values are not equal , Then put src-1 The element pointed to is assigned to dst In the right place ;

then src and dst At the same time, move one bit backward , As shown in the figure

here src The element that points to is 1,src-1 The element that points to is 1, Their values are equal ;

that src Just move one person back ,dst unchanged , As shown in the figure

here src The element that points to is 2,src-1 The element that points to is 1, Their values are not equal , Then put src-1 The element pointed to is assigned to dst In the right place ;

then src and dst At the same time, move one bit backward , As shown in the figure

here src The element that points to is 2,src-1 The element pointed to is also 2, Their values are equal

that src Just move one person back ,dst unchanged , As shown in the figure

here src The element that points to is 3,src-1 The element that points to is 2, Their values are not equal , Then put src-1 The element pointed to is assigned to dst In the right place ;

then src and dst At the same time, move one bit backward , As shown in the figure

here src Has pointed to the outside of the array , Then directly assign the last value to dst, then dst Move one more bit backwards

Because you have to put a value , Then we must finish this section , Go to its next position , When the next value is not equal , Will be put there

So the structural design of this problem is as follows

The essence of this problem is src Follow src-1 The value of the position of , When they are not equal , The previous repeated value interval has been completed , Then put the last reservation in dst The location of .

3. Code implementation

Interface code

int removeDuplicates(int* nums, int numsSize){
    
    int dst = 0;
    int src = 1;
    while (src < numsSize) {
    
        if (nums[src-1] == nums[src]) {
    
            src++;
        }
        else {
    
            nums[dst] = nums[src-1];
            src++;
            dst++;
        }
    }
    nums[dst] = nums[numsSize-1]; //  Assign the last value to dst
    return ++dst; // dst Move one bit backwards 
}

Submit results