“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

preface

Delete duplicate item II from ordered array as follows:

Give you an ordered array nums, ask you to delete duplicate elements in place, make each element appear at most twice, return the new length of the deleted array.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

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 within the function is visible to the caller.

Example 1:

Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3] Explanation: The function should return the new length = 5, and the first five elements of the original array are modified to 1,1,2,2,3. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Input: nums =,0,1,1,1,1,2,3,3 [0] output: 7, nums =,0,1,1,2,3,3 [0] interpretation: The function should return the new length = 7, and the first five elements of the original array are modified to 0, 0, 1, 1, 2, 3, 3. You don't need to worry about the element after the new length in the array.Copy the code

A, thinking

To remove more than two elements from an ordered array, you must modify them in place

It is natural to think of sliding Windows to solve this kind of counting problem.

The left boundary of our sliding window points to the left of the continuous element and the right boundary points to the right of the continuous element. When the number of elements in a window is greater than 2, all subsequent elements are moved forward.

The general steps are as follows:

  1. Traverse the array from left to right
  2. whennums[i] == nums[left]When making the window’s right borderright++
  3. whennums[i] ! = nums[left], and the element in the window is greater than2A,right -left > 2, then calculate the distance movedmove += right-left-2
  4. In the process of traversing, as long asmove > 0, we move that element forward,nums[right-move] = nums[right]
  5. If the element in the last window is greater than2, the moving distance is updatedmove += right-left-2(Because the size of the last continuous window may be greater than2)
  6. Returns the new array lengthlen - moveAs a result

For example

Nums = {0,0,1,1,1, 2,2} is used as an example

Initial value: left = right = 0, move = 0

  1. Start traversing the arraynums
  2. whenright = 2When, appearednums[2] ! = nums[0], but the window element is not greater than2. So you only need toleft = right
  3. whenright = 6When, appearednums[6] ! = nums[2], the window element is greater than2And calculate the travel distancemove = 2And thenleft = right
  4. Due to themove > 0, and subsequent traversals will require moving elements forward
  5. The final array is updated to,0,1,1,2,2,2,2 {0}, returns the new lengthlen - move = 8 -2 =6Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 3) {// Special circumstances
            return len;
        }
        int left = 0;
        int right = 0;
        int move = 0;
        while (right < len) {
            if(nums[left] ! = nums[right]) {// Check whether the current window length exceeds 2
                if (right - left > 2){
                    move += right-left-2;
                }
                left = right;
            }
            // The element moves forward
            if (move > 0) {
                nums[right-move] = nums[right];
            }
            right++;
        }
        // It is possible that the last character is not processed
        if (right - left > 2) {
            move += right-left-2;
        }
        return len - move;
    }
Copy the code

The test code

Public static void main(String[] args) {int[] nums = {0,0,1,1,1,1,2,2}; new Number80().removeDuplicates(nums); }Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section