This is my third article about getting started

1. Title Description

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

Second, train of thought analysis

  • Here can’t use other variables, because we need to use the method of marking to distinguish, cycle make it impossible for us to avoid the way we need in the process of circulation of the current variables are marked, and decide whether to delete, delete is simple we don’t need to manage, it is ok to wait for the next cleaning. All that’s left is that if you don’t want to delete it then you need to keep it, and keeping it in this case means you need to shift it to which index you want to move it to and then you need to put the current latest index under the tag.

  • For the two Pointers mentioned above, we can call them double Pointers or fast or slow Pointers.

  • Obviously, since the array is sorted, the duplicate elements must be linked together, so it is not difficult to find them, but if every duplicate element is found, it is deleted immediately, that is, in the middle of the array, the total time is O(N^2).

  • A brief explanation of in-place modification:

  • Instead of making changes in place, we simply create an int[] array, place the unduplicated elements in the new array, and return the new array.

  • But delete in place, we don’t allow us to do new arrays, we can only do things on the original array, and then return a length, so we can use that length and the original array to figure out what the elements are.

  • This requirement is very common in array dependent algorithms, and the common solution is the fast and slow pointer technique described in our previous two-pointer technique.

AC code

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

Four,

  • We use the fast and slow pointer. With two Pointers we can record the variables that we need to shift. Solve problems smartly