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

The title

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length.

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

Their thinking

Reading the title, we can know the following conditions:

  1. Orderly array
  2. Each element appears only once
  3. The return value is the length of the deleted array
  4. No extra space, space complexity O(1)
  5. Modify the existing array

So, to sum up, we have to give up the need for extra storage space such as burst.

So the last thing I wanted to do was use a double pointer.

Double pointer

The problem solving process is as follows:

  • Create a pointer I to the first number, and another pointer J to the second number.
  • If nums[I] and nums[j] are not equal, increment I by 1 and assign nums[j] to nums[I].
  • Because the initial number at I equals 0 is not counted, the final result is returned with +1.
/ * * *@param {number[]} nums
 * @return {number}* /
var removeDuplicates = function(nums) {
    let len = nums.length;
    if(! len)return 0;
    let i = 0;
    for (let j = 1; j < len; j++) {
        if (nums[i] !== nums[j]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
};
Copy the code

Advanced writing a line of code:

var removeDuplicates = function(nums) {
    return nums.reduce((j, v, i) = >(i ! = =0&& v ! == nums[j] && (nums[++j] = v), j),0) + 1
};
Copy the code

This is Xiaokui 🌻, as long as you turn your heart toward the sun, you will have warmth ~

Let’s overcome the algorithm together!!