• Personal blog: Javaniuniu.com/
  • Difficulty:simple
  • The problem involves the algorithm:
  • Ideas:Copy to cover Reverse traversal
  • Similar questions:

The title27. Remove elements

Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array.

Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.

The order of elements can be changed. You don’t need to worry about the element after the new length in the array.

Example 1:

Given nums = [3,2,2,3] and val = 3, the function should return a new length of 2 and the first two elements in nums are both 2. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Given nums = [0,1,2,2,3,0,4,2] and val = 2, the function should return the new length 5 and the first five elements in nums are 0,1, 3,0,4. Notice that these five elements can be in any order. You don't need to worry about the element after the new length in the array.Copy the code

Description:

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

Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. Int len = removeElement(nums, val); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

Method one is traversed in reverse order

  • Answer:

    • Reverse traversal can solve the problem of deleting an array without making redundant judgment on the array subscript

  • Complexity analysis:

    • Time complexity: O(n)O(n)O(n), assuming that the length of the array is NNN, the worst case is when all the elements in the array are different, then NNN is traversed
    • Space complexity: O(1)O(1)O(1).

python

class Solution:
    def removeElement(self, nums: List[int], val: int) - >int:
        for i in range(len(nums)-1, -1, -1) :if(nums[i] == val):
                nums.pop(i)
        return len(nums)

Copy the code

Method 2 copy overwrite

  • Answer:

    • The main idea is to iterate over nums, each time the number variable is num, and set a subscript ANS
    • Nums [ANS] = num, ans increases by 1 if the number is different from the value to be removed
    • If the values are the same, the number is skipped, and ans is the new array length
    • This approach works best when a large number of elements need to be removed, and the most extreme case is when all elements need to be removed

  • Complexity analysis:

    • Time complexity: O(n)O(n)O(n), assuming that the length of the array is NNN, the worst case is when all the elements in the array are different, then NNN is traversed
    • Space complexity: O(1)O(1)O(1).

python

class Solution:
    def removeElement(self, nums: List[int], val: int) - >int:
        ans = 0
        for num in nums:
            ifnum ! = val: nums[ans] = num ans +=1
        return ans
Copy the code

java

class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = 0;
        for (int num:nums){
            if (num != val) {
                nums[ans] = num;
                ans++;
            }
        }
        returnans; }}Copy the code

Method three swap and remove

  • Answer:

    • The main idea is to iterate over nums, traversal pointer is I, total length is ANS
    • If there is a difference between the number and the value to be removed during the traversal, I increases by 1 to continue the next traversal
    • If nums[I] and nums[ans-1] are the same, then the current nums[I] is swapped with the last nums[ans-1]
    • This approach is best used when there are few elements to remove, and the most extreme case is when there are no elements to remove and you just iterate

  • Complexity analysis:

    • Time complexity: O(n)O(n)O(n), assuming that the length of the array is NNN, the worst case is when all the elements in the array are different, then NNN is traversed
    • Space complexity: O(1)O(1)O(1).
class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = nums.length;
        for (int i = 0; i < ans;) {
            if (nums[i] == val) {
                nums[i] = nums[ans - 1];
                ans--;
            } else{ i++; }}returnans; }}Copy the code