[Link] https://leetcode.com/problems/remove-duplicates-from-sorted-array/
Approach
Because the input is sorted, equal values are adjacent. Scan the array from left to right with a read index, and keep a write index for the next position where a new distinct value belongs. When the current value differs from the last value written, copy it to the write position and advance the write index.
Before each read, the prefix nums[0..write) contains exactly the distinct values from the already processed input, in sorted order. The first value is always written when present; each later value is written only when it differs from the previous distinct value. Thus, an empty array is safe and returns 0; otherwise the method returns the number of distinct values. The resulting distinct values occupy the prefix of the input array, and anything after that prefix can be ignored.
The algorithm takes O(N) time and O(1) extra space.
Java
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int removeDuplicates(int[] nums) {
int write = 0;
for (int read = 0; read < nums.length; read++) {
if (write == 0 || nums[read] != nums[write - 1]) {
nums[write++] = nums[read];
}
}
return write;
}
}