LeetCode.26 Delete duplicate items in sorted array

Posted June 14, 2021 by Jian Yang (宋金阳)


Problem Description

Given a sorted array, you need to delete the repeated elemets In-place, so that each elements only appears once, and return the new length of the removed array.

Don't use extra space, you must modify the input array In-place and do it under the condition of O(n) extra memory.


Example 1

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

Output: 2, nums = [1,2]

Explanation: The function should return the new length of 2, the first two elements of the original array nums have been modified to [1,2].

Example 2

input: Given array nums = [0,0,1,1,1,2,2,3,3,4]

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

Explanation: The function should return the new length of 5, the first five elements of the original array nums have been modified to [0, 1, 2, 3, 4]

Animated demonstrations


Code

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  let buffer = 0;
  for (let index = 1; index < nums.length; index++) {
    if (nums[buffer] !== nums[index]) {
      nums[buffer] = nums[index];
      buffer++;
    }
  }
  return buffer + 1;
};
removeDuplicates([1, 1, 1, 7]);

for this problem, we can solve it by the most brute force method, which is two levels of for loop nesting, and the time complexity is O(n^2);

this second method is two-pointers. in fact, this is a trick. of course, we like tricks. buffer is a slow pointer, which is used to record the subscript of the last elements of a non-repeating element in the array. the fast pointer index is used to traverse the entire array, as long as the pointer index, move to value of pointer i forward and assign the element pointed to by pointer index to the position ponited to by buffer.