https://app.laicode.io/app/problem/115
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
https://www.lintcode.com/problem/remove-duplicates-from-sorted-array/description
Given a sorted integer array, remove duplicate elements. For each group of elements with the same value keep only one of them. Do this in-place, using the left side of the original array and maintain the relative order of the elements of the array. Return the array after deduplication.
Assumptions
- The array is not null
Examples
- {1, 2, 2, 3, 3, 3} → {1, 2, 3}
Easy
Array
Because there can be at most 1 copy for each unique element, the array should have at least 1 element in it.
Use fast-slow pointer
- All the elements to the left of the slow pointer, including the one pointed to by the slow pointer, are processed portion of the input
- All the elements to the right of the fast pointer are the portion of the input that is to be processed
- All the elements in the middle of the slow and fast pointer are the ones that have been processed but useless in terms of return value
public class Solution {
public int[] dedup(int[] array) {
// Write your solution here
if (array == null || array.length <= 1) {
return array;
}
// Two pointers:
// 1. array[0, slow]: processed for result
// 2. array(slow, fast): processed useless
// 3. array[fast, end]: yet to be processed
int slow = 0;
for (int fast = 1; fast < array.length; fast++) {
// We are only interested in the case
// when two elements are different
if (array[slow] != array[fast]) {
array[++slow] = array[fast];
}
}
// array[0, slow] is the part for result
int[] result = new int[slow + 1];
for (int i = 0; i <= slow; i++) {
result[i] = array[i];
}
return result;
}
}Time: one iteration over the entire array of n elements + one iteration from 0 to slow number of elements in the array ⇒ O(n)
Space: only a slow pointer is created ⇒ O(1)
