Remove Duplicates from Sorted Array (Java)
Tags: Algorithm, Array, Java, LeetCode, remove duplicateLeetcode: 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.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class RemoveDuplicates{ public int removeDuplicates(int[] nums) { int pre = 0; int cur = 1; while(cur < nums.length) { if(nums[cur] != nums[cur - 1] ) { nums[++pre] = nums[cur]; } cur++; } return pre + 1; } } |
