This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

Topic describes

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.

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. That is, no copies of the arguments are made
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

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

Tip:

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

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Ideas & CODE

  1. Double pointer

After the experience of [Q26], the problem solution is immediately apparent, direct fast and slow pointer arrangement.

We also define two Pointers:

  • Fast pointer: Traverses the subscript position reached by a set of numbers
  • Slow pointer: The subscript to be filled in for the next value that differs from the given value

From the above definition, we can conclude that we find an element different from val by operating on the fast pointer, then replace that element with the index of the slow pointer, and finally increment the fast or slow pointer index by one.

The following code

public int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) { 
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}
Copy the code