Topic describes

27. Remove elements

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

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

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 of 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

The question interpretation

Draw the main points of the topic:

  • In situ removal
  • Do not use extra array space
  • You don’t need to worry about the element after the new length in the array

We are asked to delete all elements equal to val in place, without using extra space, and without worrying about elements that exceed the length of the new array.

That is, if the original array nums is x and the number of val elements to be deleted is Y, we simply overwrite the n elements to be deleted with other valid elements and return the final array length x-y.

We are not asked to actually delete the elements of the array, but to overwrite the values of the related elements.

Train of thought in this paper, the

So how do you rewrite elements?

Since we want val elements to be stacked at the end of the array, we send out a pathfinder to overwrite any non-Val elements we encounter.

Therefore, we can define two Pointers:

  • Quick pointerj: Used to find notvalThe element
  • Slow pointeri: whenjTo find thevalElement, is notvalElements covered

Graphic thinking

For example, nums = [3,2,2,3], val = 3.

Both I and j point to subscript 0 at the beginning:

J refers to val, so move j 1 bit to the right:

At this point, pioneer J finds a non-val element, so assign it to I:

After the assignment, we get a new sequence [2, 2, 2, 3], we can know:

  • jThe element pointing to must not beval
  • iThe element pointing to must not be eithervalBecause it’s fromjThe element pointing to is assigned to,jPoint to thevalThe element is assigned

In this way, I and J have completed the mission of this round and move on!

So after each swap, we increment the double pointer synchronously, let I = I + 1, j = j + 1:

J now refers to a non-val element, and continues the assignment:

Since I and j refer to the same element, the assignment does not change the sequence. After the assignment, we continue to grow the double pointer synchronously:

J refers to an element val and cannot be assigned. Increment j, let j = j + 1:

And then we realize that j is out of range, and we’re done. [2, 2, 2, 3] is our final result, and the red part is the length of the new array, length len(nums) – (j-i).

To summarize

Set the double Pointers I and j, where j is used to find non-val elements to override the element to which I points.

  • Initial: seti = 0, j = 0
  • Traversal number group:
    • ifnums[j] ! = val:
      • thejThe value is assigned toi:nums[i] = nums[j]
      • Synchronous growth dual pointer:i = i + 1, j = j + 1
    • ifnums[j] == val:
      • jChange to fast pointer:j = j + 1, looking for the next nonvalThe element

The specific implementation

Python

class Solution:
    def removeElement(self, nums, val):
        """ :type nums: List[int] :type val: int :rtype: int """
        length = len(nums)
        i = 0
        j = 0
        while j < length:
            ifnums[j] ! = val: nums[i] = nums[j] i = i +1
                j = j + 1
            else:
                j = j + 1
        res = length - (j - i)
        return res
Copy the code

Golang

func removeElement(nums []int, val int) int {
    length := len(nums)
    if length == 0 {
        return 0
    }

    i := 0
    j := 0
    for j < length {
        if nums[j] == val {
            // find a value that is not val
            j++
        } else {
            / / assignment
            nums[i] = nums[j]
            i++ 
            j++
        }
    }

    return length - (j - i)
}
Copy the code

The complexity of the

  • Time complexity:O(n)
  • Space complexity:O(1)No extra space is used.

🐱

  • My project: github.com/JalanJiang/…
  • If you’re interested in solving problems and sharing solutions, join the LeetCode problem solving team at github.com/leetcode-no…
  • If you think the article is written well, welcome to pay attention to the public number “programming to save the world”, the public number focuses on programming foundation and server-side research and development, regularly share algorithms and data structures dry ~