Leetcode question brushing record ｜ 27_ Removing Elements

author github link ： github link

Force to buckle 27 topic

type ： Array question

subject ：

Give you an 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 .

explain

Why is the return value an integer , But the output answer is array ?

Please note that , The input array is based on 「 quote 」 By way of transmission , This means that modifying the input array in a function is visible to the caller .

You can imagine the internal operation as follows :

// nums  In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments 
int len = removeElement(nums, val);

//  Modifying the input array in a function is visible to the caller .
//  Based on the length returned by your function ,  It prints out the array   Within this length   All elements of .
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1

 Input ：nums = [3,2,2,3], val = 3
 Output ：2, nums = [2,2]
 explain ： Function should return the new length  2,  also  nums  The first two elements in are  2. You don't need to think about the elements in the array that follow the new length . for example , The new length returned by the function is  2 , and  nums = [2,2,3,3]  or  nums = [2,2,0,0], It will also be seen as the right answer .

Example 2

 Input ：nums = [0,1,2,2,3,0,4,2], val = 2
 Output ：5, nums = [0,1,4,0,3]
 explain ： Function should return the new length  5,  also  nums  The first five elements in are  0, 1, 3, 0, 4. Note that these five elements can be in any order . You don't need to think about the elements in the array that follow the new length .

Their thinking

Train of thought reminder ： Define a pointer before and after （ Front and rear double pointers ）
Train of thought details ：

1. Define two pointers , for example left and right
2. take left Put at the beginning ,right Put at the end of the array , That is to say, make :
   left = 0
right = nums The length of
3. left To the right ,right Move to the left .
4. When left Pointer to It's not equal to val Of the elements ,left Traverse right in turn
5. When left Pointer to be equal to val Of the elements , take left Replace the element pointed to with the present right-1 Pointing elements .
6. After exchange ,right-1
7. until left$\ge$right Back when left（ Return to remove all val The value of the value ）

python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        #  Define a pointer before and after （ Front and rear double pointers ）
        left = 0
        right = len(nums)
        while(left<right):
            if nums[left] == val:
                nums[left] = nums[right-1]
                right = right -1
            else:
                left = left+1
        return left

c++

class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        //  Double pointer   One at the beginning   One at the end 
        int right = nums.size();
        int left = 0;
        while (left<right){
    
            if(nums[left] == val){
    
                nums[left] = nums[right -1];
                right--;
            }else{
    
                left++;
            }
        }
        return left;

    }
};

A small detail ：

5. When left Pointer to be equal to val Of the elements , take left Replace the element pointed to with the present right-1 Pointing elements .

You can also exchange the elements pointed to by two pointers , But the running time will be left Replace the element pointed to with the present right-1 Pointing elements To get longer .

class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int left = 0;
        int right = nums.size();
        while(left<right){
    
            if(nums[left]==val){
    
                swap(nums[left], nums[right-1]);// Swap the elements pointed to by two pointers 
                right--;
            }
            else left++;
        }
        return left;

    }
};

Method 1 And the following methods 2 Comparison of running time ：