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]

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.