Remove Duplicates from Sorted Array (Java)

Tags: , , , ,

Leetcode: Remove Duplicates from Sorted Array

Given a sorted array, 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 in place with constant memory.

For example,
Given input array 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 new length.

 Analysis
 

We defined two indexes: pre and cur. pre always points to the end of the sub array nums[0 .. pre] that has no duplications. 

Initially pre == 0, which means nums[0] has no duplicates.

We start cur from 1 to the end of the array. For each cur, we compare nums[cur] with nums[cur - 1], if they are the same, which means the current value is a duplicate, we continue the scan.  Otherwise, we increase pre by 1, and assign the current value (nums[cur] ) to nums[pre]

At the end, pre is the last index of the target array with no duplicate, so the length is pre + 1. 

Java Implementation

The following code shows the java solution to this problem.