Topic describes

This is 27. Remove element on LeetCode. The difficulty is simple.

Key words: array, double pointer, modify in place

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

Tip:

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

Two-pointer violence

See in situ modification array element, the first thing we think of is double pointer, maintain two Pointers (slow fast pointer, pointer), use the fast scanning array, access to reinsert array element (in this subject is the present value is equal to the target), slow pointer array is responsible for maintaining, once fast pointer scanning to insert elements using slow pointer.

class Solution {
    public int removeElement(int[] nums, int val) {
        // Define a slow pointer
        int slow = 0;
        int len = nums.length;
        // Fast pointer traversal number group
        for (int fast = 0; fast < len; fast++) {
            int value = nums[fast];
            // If the array meets the insertion criteria
            if(value ! = val) {// Insert the number in the slow position and move the pointer back one bit laternums[slow++] = value; }}returnslow; }}Copy the code

Two-pointer optimization

For the above algorithm, there is actually a part of waste, that is, the qualified data is repeatedly assigned, for example: [1,2,3,4], val is 1, the double pointer from left to right,2,3,4 will be reassigned into the array to get the result [2,3,4], in fact, we only need to replace element 1 with 4, in other words, we need to avoid readding the already qualified data into the array.

For this array, we can divide it into two parts: the left part of the result area and the right part of the nonconformity area, so we can maintain two Pointers in two directions to traverse the array until the indices overlap.

Then the data on the left pointer is compared. If the conditions are met, the data is not processed directly and the pointer moves to the right. If the conditions are not met, the data pointed to the right pointer is taken to the left and the left pointer is pointed to for judgment. The right pointer moves to the left. Until the left and right Pointers overlap.

class Solution {
    public int removeElement(int[] nums, int val) {
        // Define the left and right Pointers
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] == val) {
                // The left pointer to the data does not meet the criteria
                nums[left] = nums[right];
                // Right pointer moves left
                --right;
            } else {
                // The left pointer moves to the right++left; }}returnleft; }}Copy the code

reference

My Github repository has been set up synchronously, click access