Leetcode daily practice - 27. Remove elements

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 27. Remove elements

Let’s get it！

---

---

1. Topic analysis

Array nums And a value val, You need In situ Remove all values equal to val The elements of , And return the new length of the array after removal .
 
Don't use extra array space , You have to use only $O(1)$ Additional space and In situ Modify input array .
 
The order of elements can be changed . You don't need to think about the elements in the array that follow the new length .

Example 1：

Example 2：

2. Title diagram

Train of thought

Open up a and nums A new array of the same size , It's not val Copy the value of to the new array

First of all, the pointer src Point to nums The starting position in the array ; The pointer dst Point to newNums The starting position in the array

here ,src The element pointed to is 0, No 2, So put the numbers 0 Put it in newNums Array , The pointer src and dst Move backward at the same time , As shown in the figure

here ,src The element pointed to is 1, No 2, So put the numbers 1 Put it in newNums Array , The pointer src and dst Move backward at the same time , As shown in the figure

here ,src The element pointed to is 2, And val The values are equal , Then put the pointer src Move back , The pointer dst Immobility , As shown in the figure

here ,src The element pointed to is 2, And val The values are equal , Then put the pointer src Move back , The pointer dst Immobility , As shown in the figure

here ,src The element pointed to is 3, No 2, So put the numbers 3 Put it in newNums Array , The pointer src and dst Move backward at the same time , As shown in the figure

here ,src The element pointed to is 0, No 2, So put the numbers 0 Put it in newNums Array , The pointer src and dst Move backward at the same time , As shown in the figure

here ,src The element pointed to is 4, No 2, So put the numbers 4 Put it in newNums Array , The pointer src and dst Move backward at the same time , As shown in the figure

here ,src The last element has been pointed to 2, And val The values are equal , So end the cycle , As shown in the figure

The time complexity of this method is $O(n)$, The complexity of space is also $O(n)$; It doesn't fit the question

Train of thought two

This method is an upgrade of idea one , Do not open up new arrays , Use double pointers directly in the original array

The pointer src and dst At the same time point to nums Starting position , As shown in the figure

here src The element pointed to is 0, It's not equal to val（2）, Then use src Point to the element Cover fall dst Pointing elements , then src and dst Move backward at the same time , As shown in the figure

here src The element pointed to is 1, It's not equal to val（2）, Then use src Point to the element Cover fall dst Pointing elements , then src and dst Move backward at the same time , As shown in the figure

here src The element pointed to is 2, be equal to val（2）, Then just put the pointer src Move back , The pointer dst Immobility , As shown in the figure

here src The element pointed to is still 2, be equal to val（2）, Still only put the pointer src Move back , The pointer dst Immobility , As shown in the figure

here src The element pointed to is 3, It's not equal to val（2）, Then use src Point to the element Cover fall dst Pointing elements , then src and dst Move backward at the same time , As shown in the figure

here src The element pointed to is 0, It's not equal to val（2）, Then use src Point to the element Cover fall dst Pointing elements , then src and dst Move backward at the same time , As shown in the figure

here src The element pointed to is 4, It's not equal to val（2）, Then use src Point to the element Cover fall dst Pointing elements , then src and dst Move backward at the same time , As shown in the figure

here src Point to last element 2, be equal to val（2）, So it's just over , return dst The length of

therefore dst Is used to delete the array equal to val Value , Then put not equal to val Values of are put back in turn ！ So the structure of this problem is as follows

3. Code implementation

Interface code

int removeElement(int* nums, int numsSize, int val){
    
    int src = 0;
    int dst = 0;
    int i = 0;
    while (src < numsSize) {
    
        if (nums[src] != val) {
    
            nums[dst] = nums[src];
            src++;
            dst++;
        }
        else {
    
            src++;
        }
    }
    return dst;
}

Submit results