Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

The title is from li Kou and is described as follows:

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

Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2] Explanation: 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. For example, the function returns a new length of 2, and nums = [2,2,3,3] or nums = [2,2,0,0] will also be considered the correct answer.Copy the code

Example 2

Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3] Explanation: 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

Thought analysis

This is very similar to problem 26, one is to remove the duplicate, and this is to remove the specified element. Personally, this question is much easier than the last one. With double Pointers, the left pointer starts at index 0 and the right pointer starts at the last bit (len(nums)-1). Traverse nums [left]

  • nums[left]Equal to the target value val, ifnums[right] ! = valIs assigned tonums[left]If,nums[right] == val, then left stays the same and right moves to the left.
  • nums[left]Not equal to the target value val, left moves right, and the loop continues.

And move the right subscript to the left. Note that the critical point is:

  • In order to[1, 2, 3], target: 1For example, after loop 1, left and right subscripts both point to the value 2. At this timenums[left] ! = valWithout moving,left += 1Continue the next loop. Since then,left > rightIf the condition is not met, the loop exits.

The index pointing to right is 1, which means that the valid array length is 2.

  • If the example is,1,3 [1], the target: 1. At the end of the loop, both left and right subscripts point to the element with index 1 — 1, leaving the final value of 1 and right pointing to the element with index 0. The valid array length is 1.

AC code

// removeElement
// Double pointer solution
func removeElement(nums []int, val int) int {
   length := len(nums)
   left, right := 0, length- 1
   for left = 0; left <= right; {
      ifnums[left] ! = val { left +=1
      } else {
         ifnums[right] ! = val { nums[left] = nums[right] left +=1
         }
         right -= 1}}return right + 1
}
Copy the code

conclusion

The main direction is to move the valid elements in the tail to the front, making sure that the preceding elements are valid. In addition, it is important to note that after a loop, the left moves to the right, or the right moves to the left, depending on the situation.

No additional container is required to store values, and the space complexity is O(1). The number of cycles depends on the length of NUMs, so the time complexity is O(n).