Given an ordered array of nums, please delete the repeated elements in place so that each element appears only once, and return the new length of the array after deletion.

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

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, do 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]);
}
Copy the code

Example 1:

Input: nums = [1,1,2]

Output: 2, nums = [1,2]

Explanation: The function should return a new length of 2, and the first two elements of the original nums array should be changed to 1, 2. You don’t need to worry about the element after the new length in the array.

Example 2:

Input: nums = [0,0,1,1, 2,2,3,3,4]

5, nums = [0,1,2,3,4]

Explanation: The function should return a new length of 5, and the first five elements of the original nums array are changed to 0, 1, 2, 3, 4. You don’t need to worry about the element after the new length in the array.

Tip:

0 <= nums.length <= 3 * 104

-104 <= NUMs [I] <= 104 NUMs are sorted in ascending order

Answer:

Solution: Double pointer

First of all, notice that the array is ordered, so the elements that repeat must be adjacent.

Asking for a duplicate element to be removed essentially moves the non-duplicate element to the left of the array. Consider using two Pointers, one denoted as P before and one as Q after. The algorithm flow is as follows: 1. Compare whether the elements at fast and fast-1 are equal. If they are equal, fast increases right by 1 if they are not equal, copy the elements of fast to slow, which increases right by 1, and repeat the process until FAST equals the length of the array. Return slow, which is the new array length.

/ * * *@param {number[]} nums
 * @return {number}* /
var removeDuplicates = function(nums) {
    const l = nums.length
    if(l === 0)return 0
    let fast =1;
    let slow = 1;
    while(fast<l){
        if(nums[fast] ! == nums[fast-1]){
            nums[slow] =nums[fast]
            slow++
        }
        fast++
    }
    return slow
};
Copy the code