1. The subject

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 array nums are changed to 1,2. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

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

Tip:

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

2. Solution 1: Use double Pointers

Two Pointers, fast and slow, are defined as fast and slow Pointers respectively. The fast pointer represents the subscript position reached by the traversal number group, and the slow pointer represents the subscript position to be filled in by the next different element. Initially, slow points to 0, fast points to 1, and fast traverses backwards to determine whether it is equal to slow. Unequal assign fast to slow and continue traversing.

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

Well, look at the efficiency is terrible… Delete the duplicate elements in the array. Delete the duplicate elements in the array.

3. Solution 2: two-pointer optimization

Two Pointers, fast and slow, are defined as fast and slow respectively. The fast pointer represents the subscript position reached by the traversal number group, and the slow pointer represents the subscript position to be filled in the next different element. Initially, slow points to 0, fast points to 1, and fast traverses backwards to determine whether it equals slow. If it’s not, we assign slow, slow plus 1. And then we return slow + 1.

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

Now time and space are much more complicated