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

The title

Link: leetcode-cn.com/problems/re…

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.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, it does not make any copies of the arguments int len = removeDuplicates(nums);

// 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]); }

 

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 changed to 1,1,2,2,3. You don’t need to worry about the element after the new length in the array.

Example 2:

Input: * * * * nums =,0,1,1,1,1,2,3,3 [0] output: * * * * 7, nums =,0,1,1,2,3,3 [0] * * : 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.

 

Tip:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • numsThey are arranged in ascending order

Their thinking

Idea 1

They say: no more than two occurrences of each element

Nums [j] replaces nums[I] with nums[I] when the current and the next are not equal.

Until the end of the loop, j is the length of the array after processing, which is directly truncated

i = 0, m = 1, j = 0, nums = [1.1.1.2.2.3]

i = 1, m = 2, j = 0, nums = [1.1.1.2.2.3]
i = 2, m = 3, j = 0, nums = [1.1.1.2.2.3]
i = 3, m = 1, j = 2, nums = [1.1.1.2.2.3]
i = 4, m = 2, j = 2, nums = [1.1.1.2.2.3]
i = 5, m = 1, j = 4, nums = [1.1.2.2.2.3]
i = 6, m = 1, j = 5, nums = [1.1.2.2.3.3]
/ / truncation
i = 6, m = 1, j = 5, nums = [1.1.2.2.3]
Copy the code
/ * * *@param {number[]} nums
 * @return {number}* /
var removeDuplicates = function(nums) {
    let n = nums.length;
    if(! n)return n
    let j = 0
    let i = 0
    let m = 1
    while (i < n) {
        if(nums[i] ! == nums[i +1]) {
            if (m > 1) nums[j++] = nums[i] 
            nums[j++] = nums[i]
            m = 0
        }
        m++
        i++
    }
    return nums.length = j
}
Copy the code

Idea 2

How fast a pointer

var removeDuplicates = function(nums) {
    let n = nums.length;
    if (n < 3) return n
    let slow = 2
    let fast = 2
    while (fast < n) {
        if (nums[slow - 2] !== nums[fast]){
            nums[slow++] = nums[fast]
        }
        fast++
    }
    return nums.length = slow
};
Copy the code

Idea 3

Set the starting position of the fast and slow Pointers to the same. If the condition is met all the way through the move, the fast and slow Pointers will continue to move equally until the length of the array is printed. If three repetitions occur, only the fast pointer is moved. You can draw it on a piece of paper.

You can still use the code for problem 26 to delete duplicates in an ordered array. You can change all the 2’s to 1’s, just like in a comment, you can pass without writing the first line, because there’s no array less than 3 in the use case.

code

/ * * *@param {number[]} nums
 * @return {number}* /
var removeDuplicates = function(nums) {
    // if (nums.length <= 2) return nums.length;
    // s indicates slow and f indicates fast
    let s = 2;// Represents both the index (slow pointer) and the length of the last record
    // Start with 1 because nums must have a value that is filtered by the front end and the final output length is at least 2
    for (let f = 2; f < nums.length; f++) {// A circular index is equivalent to a fast pointer
        if (nums[s - 2] !== nums[f]) {
            nums[s] = nums[f];// Modify in place
            s++;// Output length +1
        }
        // Only fast Pointers, i.e. circular indexes, are moved when equal
    }
    return s;
};
Copy the code