26. Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

Detail explanation for two-pointer, runtime 79.28 %

Image for post

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.It doesn’t matter what values are set beyond the returned length.

Solution 1: two-pointer

The idea for such a problem is that we will set two pointers, the faster one will go through all elements in the list, and the slower one only move when meeting the unique number.

Not bad, but wait, why this pass all the tests! The question told us to remove the duplicates in-place such that each element appear only once, But we can see after the for loop, nums looks like below.

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

I think this is just the test case created by LeetCode is not enough. So we still need to delete the duplicates in-place. But this time it will become much easier.

3

No Responses

Write a response