1. Title Description

Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array.

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

Difficulty: Easy

Example 1:

Given array nums = [1,1,2],

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:

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

The function should return a new length of 5, and the first five elements of the original nums array should be changed to 0, 1, 2, 3, 4.

You don’t need to worry about the element after the new length in the array.

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

2. How to solve the problem

The space complexity of the array is O(1). Return the length of the array after removing the duplicate elements. In simple terms, it’s de-duplicating in place, and it doesn’t have to deal with the elements beyond the length of the array

Thinking a

Use fast and slow Pointers: At first, both Pointers point to the first digit. If the two Pointers point to the same digit, the fast pointer moves forward. If they are different, the slow pointer moves forward and is set to the value that the fast pointer points to

Idea 2

Count the number of duplicate elements in the array. Subtract the number of duplicate elements from the length of the array. The key is to calculate the value of the repeated element to be replaced, which is another way of writing a fast or slow pointer

Thought three

Cycle through the number group, compare the two elements before and after, remove the same; Because each time we remove an element from the array is order n; So this is going to take some time

AC code

Thinking a

var removeDuplicates = function (nums) {
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] !== nums[i]) {
      nums[++i] = nums[j];
    }
  }
  // I is the subscript and the array length needs to be +1
  return i + 1;
};
Copy the code

Idea 2

var removeDuplicates = function (nums) {
  let repeat = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] == nums[i + 1]) {
      repeat++;
    } else {
      nums[i + 1 - repeat] = nums[i + 1]; }}return nums.length - repeat;
}
Copy the code

Thought three

var removeDuplicates = function (nums) {
  let len = nums.length
  for (let i = 0; i < len - 1; i++) {
    if (nums[i] == nums[i + 1]) {
      nums.splice(i + 1.1); i--; len--; }}return len + 1;
}
Copy the code

Four,

Fast or slow pointer is better, the code is the most concise, the execution time is also a little faster