Leetcode remove element & move zero

Title address (27. Remove elements )

https://leetcode-cn.com/problems/remove-element/

Title Description

 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 .

 Tips ：

  0 <= nums.length <= 100
  0 <= nums[i] <= 50
  0 <= val <= 100

---

Violence solution ： Two layers of for loop

//  Time complexity : O(N^2)
//  Spatial complexity : O(1)
class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int len = nums.size();
        for(int i=0; i<len; i++){
    
            if(nums[i] == val){
     // Find the element that needs to be removed , Just move the array forward one bit 
                for(int j=i+1; j<len; j++)
                    nums[j-1] = nums[j];
                i--; // Because the subscript i All the later values are moved forward by one bit 
                len--; // The size of the array -1
            }
        }
        return len;
    }
};

---

Apply for an additional dynamic array
Apply for an additional dynamic array , Traverse nums Array time , It will not be equal to val Copy the value of to the dynamic array
Then copy the contents of the dynamic array back nums Array , return nums.size() that will do

//  Time complexity : O(N)
//  Spatial complexity : O(N)
class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int len = nums.size();
        vector<int> data;
        for(int i=0; i<len; i++){
    
            if(nums[i] != val)
                data.push_back(nums[i]);
        }
        nums.assign(data.begin(), data.end()); // nums = data;
        return nums.size();
    }
};

---

Although the first two methods can pass , But not in line with the title O(1) The condition of extra space .
Double finger needling ( Fast and slow pointer method )
[ Through a fast pointer and a slow pointer in a for Loop to achieve two for Cycle work ]

//  Time complexity : O(N)
//  Spatial complexity : O(1)
class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int slowindex = 0, len = nums.size();
        for(int quickindex=0;quickindex<len;quickindex++){
    
            if(nums[quickindex] != val)
                nums[slowindex++] = nums[quickindex];
        }
        return slowindex;
    }
};

Official explanation
When num=[4,1,2,3,5],val=4, It seems unnecessary to [1,2,3,5] Move these elements one step left , Because the order of elements mentioned in the problem description can be changed , It will be 4 And at the end of the array 5 swap , then len-=1, It's equivalent to putting 4 Deleted

When we meet nums[i] = val when , We can swap the current element with the last element , And release the most > The latter element . This actually reduces the size of the array 1
Please note that , The last element exchanged may be the value you want to remove . But don't worry , In the next iteration , We'll still check this element .

//  Time complexity : O(N)
//  Spatial complexity : O(1)
class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int len = nums.size(), i = 0;
        while(i<len){
    
            if(nums[i] == val){
    
                nums[i] = nums[len-1];
                len--;
            }
            else
                i++;
        }
        return len;
    }
};

---

Title address (283. Move zero )

https://leetcode-cn.com/problems/move-zeroes/

Title Description

 Given an array  nums, Write a function that will  0  Move to end of array , While maintaining the relative order of non-zero elements .

 Example :

   Input : [0,1,0,3,12]
   Output : [1,3,12,0,0]

 explain :

   Must operate on the original array , Cannot copy extra arrays .
   Minimize the number of operations .

Two traversal

// Time complexity :O(N)
// Spatial complexity :O(1)
class Solution {
    
public:
    void moveZeroes(vector<int>& nums) {
    
        int slowindex = 0, len = nums.size();
        // The first time I traverse , Will not 0 All the elements are assigned to nums
        for(int quickindex=0; quickindex<len; quickindex++){
    
            if(nums[quickindex] != 0)
                nums[slowindex++] = nums[quickindex];
        }
        // Not 0 The statistics are finished , The rest is 0 了 , Assign all the elements at the end to 0 that will do 
        while(slowindex<len)
            nums[slowindex++] = 0;
    }
};

Tips ： And Remove elements Compare the speed pointer solutions of

---

One traverse
Refer to the idea of fast platoon ( This idea is really wonderful ), take 0 As a benchmark , Not equal to 0 Number of numbers nums[i] != 0 Put it to the left of the benchmark , be equal to 0 Of nums[i] == 0 Put it on its right

// Time complexity :O(N)
// Spatial complexity :O(1)
class Solution {
    
public:
    void moveZeroes(vector<int>& nums) {
    
        // Two pointers i and j
        int j = 0, len = nums.size();
        for(int i=0; i<len; i++){
    
            if(nums[i] != 0){
    
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j++] = temp;
            }
        }
    }
};

Optimize the code

// Time complexity :O(N)
// Spatial complexity :O(1)
class Solution {
    
public:
    void moveZeroes(vector<int>& nums) {
    
        int j = 0, len = nums.size();
        for(int i=0; i<len; i++){
    
            if(nums[i] != 0){
    
                if(i>j){
    
                    nums[j] = nums[i];
                    nums[i] = 0;
                }
                j++; // This step cannot be missed  
            }
        }
    }
};

When nums[i] != 0 when , if i==j, It indicates that the number of the previous stack at the beginning of the array is non-zero , No action is required , if i > j when , Only need to nums[i] The value of is assigned to nums[j], And assign the value of the original position to 0

Refer to the big guy's problem solution :

• https://leetcode-cn.com/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/
• https://leetcode-cn.com/problems/remove-element/solution/27-yi-chu-yuan-su-bao-li-jie-fa-shuang-zhi-zhen-ji/