patternjavaModerate
Removing duplicate values from an array
Viewed 0 times
removingarrayduplicatevaluesfrom
Problem
Here is my code for removing duplicated values from an array. I think I tested it with the most possible cases. Any suggestions or bugs?
After some tests, it appears really inefficient because an array with 1,000,000 elements takes a very long time to end. Is there any better way to implement this on arrays?
class duplicate {
public static int[] removeDuplicates(int[] arr) {
int end = arr.length;
for (int i = 0; i < end; i++) {
for (int j = i + 1; j < end; j++) {
if (arr[i] == arr[j]) {
int shiftLeft = j;
for(int k = j + 1; k < end; k++, shiftLeft++) {
arr[shiftLeft] = arr[k];
}
end--;
j--;
}
}
}
int[] whitelist = new int[end];
for (int i = 0; i < end; i++) {
whitelist[i] = arr[i];
}
return whitelist;
}
}After some tests, it appears really inefficient because an array with 1,000,000 elements takes a very long time to end. Is there any better way to implement this on arrays?
Solution
Suggestion:
Another solution might be:
Here you only iterate once via
public static Integer[] removeDuplicates(Integer[] arr) {
return new HashSet(Arrays.asList(arr)).toArray(new Integer[0]);
}Another solution might be:
public static int[] removeDuplicates(int[] arr) {
Set alreadyPresent = new HashSet();
int[] whitelist = new int[0];
for (int nextElem : arr) {
if (!alreadyPresent.contains(nextElem)) {
whitelist = Arrays.copyOf(whitelist, whitelist.length + 1);
whitelist[whitelist.length - 1] = nextElem;
alreadyPresent.add(nextElem);
}
}
return whitelist;
}Here you only iterate once via
arr.Code Snippets
public static Integer[] removeDuplicates(Integer[] arr) {
return new HashSet<Integer>(Arrays.asList(arr)).toArray(new Integer[0]);
}public static int[] removeDuplicates(int[] arr) {
Set<Integer> alreadyPresent = new HashSet<Integer>();
int[] whitelist = new int[0];
for (int nextElem : arr) {
if (!alreadyPresent.contains(nextElem)) {
whitelist = Arrays.copyOf(whitelist, whitelist.length + 1);
whitelist[whitelist.length - 1] = nextElem;
alreadyPresent.add(nextElem);
}
}
return whitelist;
}Context
StackExchange Code Review Q#29210, answer score: 11
Revisions (0)
No revisions yet.