[daily question] remove elements

Hello Code. 2022-05-14 14:57:17 阅读数:551

dailyquestionremoveelements

Personal blog :www.hellocode.top
All articles are in Top blog First episode , Other platforms update synchronously
This column :《 A daily topic 》
If there is a problem , Welcome to correct , Learning together ~~
Part of the article refers to 《 Random code recording 》, If there is any infringement , Please contact to delete ~~


Problem description

  • Time :2022-05-09
  • Title No :27
  • difficulty : Simple

Problem 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]);
}

source : Power button (LeetCode)

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

Their thinking

The solution of the problem is from Random code recording . If there is any infringement , Please contact to delete ~~

  • In solving the problem , We can all think about the violent solution first and solve the problem , Then through gradual optimization , To improve the performance of your code
  • For this question , It can be solved by violence and double pointer

Violence solution

27. Remove elements - Violence solution

  • Use violence to solve this problem , Just need a double for loop , Through to nums All values in the array are judged
  • If it is equal to val value , Just move the element to cover it ( take val The element after moves forward ), Also on size–

* Be careful :* Will be with val After the elements with equal values are overwritten , Need to put i–( Because the following elements move forward one bit )

Double pointer solution

27. Remove elements - Double finger needling

  • There are many operations of double pointers in arrays and linked lists , It's not easy to understand at first , You can think more with the above picture
  • Define two pointers (fast and slow) To complete the double for The task completed in a loop
  • First, point both pointers to the first element , Then proceed ++ Traversing elements in an array
  • When fast The element that points to is equal to val when ,slow Leave it in the current position to mark ,fast Conduct ++ Start the operation val Corresponding to the element after the index
  • fast The element pointed to is not equal to val when , take fast The element pointed to is assigned to slow The position of , Achieve double for The operation of moving the array forward in the loop
  • Last slow The value of is the value of the array after removing the elements size value

Code implementation

Through the above analysis , The removal of elements can be realized by violent solution and double pointer solution respectively

Violence solution

class Solution {

public int removeElement(int[] nums, int val) {

int size = nums.length;
for(int i = 0; i < size; i++){

if(val == nums[i]){

for(int j = i + 1; j < size; j++){

nums[i] = nums[j];
}
i--;
size--;
}
}
return size;
}
}

  • Time complexity :O(n^2)
  • Spatial complexity :O(1)

Double pointer solution

class Solution {

public int removeElement(int[] nums, int val) {

int slow = 0;
for(int fast = 0; fast < nums.length; fast++){

if(val != nums[fast]){

nums[slow++] = nums[fast];
}
}
return slow;
}
}

  • Time complexity :O(n)

  • Spatial complexity :O(1)

summary

  • Generally, when you encounter a problem , You can think about violence first , Then consider other more efficient algorithms or continuously optimize the violent solution , To improve the efficiency of the algorithm
  • double for Loop through the array , If the array element is moved forward and backward in the inner loop , The corresponding outer loop control variables need to be adjusted accordingly (– or ++)
  • There are many scenarios in which the double pointer method is used in arrays and linked lists , It was not easy to understand at first , You can understand it by moving pictures or finding corresponding videos on the Internet
版权声明:本文为[Hello Code.]所创,转载请带上原文链接,感谢。 https://qdmana.com/2022/134/202205141454210180.html