This article is participating in “Java Theme Month – Java Swipe Card”, see the activity link for details

Topic describes

Given an array nums and a value val, you need to remove all elements equal to val in place and return the new length of the removed 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 the elements can be changed. You don’t have to worry about elements beyond the new length of the array.

Example 1:

Input: nums = [3,2, 3], val = 3 Output: 2, nums = [2,2] Explanation: The function should return the new length 2, and the first two elements in nums are both 2. You don't have to worry about elements beyond the new length of the array. For example, if the function returns a new length of 2 and nums = [2,2,3,3] or nums = [2,2,0,0], it 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, with the first five elements of nums being 0,1, 3,0,4. Note that these five elements can be in any order. You don't have to worry about elements beyond the new length of the array.Copy the code

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

Thought analysis

This problem is simple, is to iterate through the array, find the same as the given value of the element, found the element, and move the array. Since there is an operation that does not move the pointer when traversing the number group, if a condition is not given to break out of the loop, it will fall into an infinite loop. Since the array is unordered, the number of operations is used to limit the number of loops, so the number of operations should be equal to the length of the original array.

The code shown

class Solution {
    public int removeElement(int[] nums, int val) {
        // The array is empty and the new array has a length of 0
        if (nums.length == 0)
            return 0;
        // New array length
        int newLength = 0;
        // Record the number of operations to break out of the loop
        int opTimes = 0;
        for (int i = 0; i < nums.length; i++) {
            // Add the operand by 1
            opTimes++;
            if(nums[i] ! = val) {// If the current element is not equal to the given value, the length of the new array is increased by 1
                newLength++;
            } else {
                // If the current element is equal to the given value, the current value is removed and all values from the current position in the array are moved one position forward
                for (int j = i; j < nums.length - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                // Continue the comparison without moving the pointer position
                i--;
            }
            // If the number of operations is greater than or equal to the length of the array, the loop is broken
            if (opTimes >= nums.length)
                break;
        }
        returnnewLength; }}Copy the code

conclusion

Persistence is victory, come on!!

The official answer key

    // Normal double pointer
    public static int removeElementOfficial(int[] nums, int val) {
        int length = nums.length;
        // The array is empty and the new array has a length of 0
        if (length == 0)
            return 0;
        // Speed pointer, judging from 0
        int fast = 0, slow = 0;
        while (fast < length) {
            if(nums[fast] ! = val) { nums[slow] = nums[fast]; slow++; } fast++; }return slow;
    }

    // The optimized double pointer
    public static int removeElementOfficial2(int[] nums, int val) {
        int length = nums.length;
        // The array is empty and the new array has a length of 0
        if (length == 0)
            return 0;
        // Double pointer to the left and right to avoid repeated assignment of elements
        int left = 0, right = length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else{ left++; }}return left;
    }
Copy the code