As the header said. I want to delete all duplicate element from an array without using any library or collection. I usually use Set or HashMap but it is not possible anymore in this case. I also thought about sort the array and check from the beginning to the end like
If(arr[i]==a[i+1])
delete arr[i]; i--;
Or maybe something like using 2 for loops. But they are not efficient enough. Are there any other more efficiently way to delete duplicates? Thank you!
If we sort the array, any duplication between the values will be close to each other. That way we can remove them
int a[] = { 1,9,55,1,8,9,77,2,5,54,7,10,11 };
Arrays.sort(a);
int j = 0;
for (int i = 0; i < a.length - 1; i++) {
if (a[i] != a[i + 1]) {
a[j] = a[i];
j++;
}
}
a[j] = a[a.length - 1];
return a;
If you can use Streams (they are not collections and can be used since Java 8), You can do something like this:
int[] result = Arrays.stream(a).distinct().toArray();
This is another possibility. The cost is O(n + m) where m is the max value of the input array.
public static void main(String[] args) {
int arr[] = {23, 56, 78, 92, 44, 3, 3, 3, 23, 11, 10, 10, 10, 10};
// Find the size for the new array to allocate.
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// Mark the values stored in the array (hit or miss array)
int[] presence = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
presence[arr[i]] = 1;
}
// Find the size for the new array to allocate
int count = 0;
for (int i = 0; i < presence.length; i++) {
if (presence[i] != 0) {
count++;
}
}
// Store the element in the new array when hit
int[] res = new int[count];
int index = 0;
for (int i = 0; i < presence.length; i++) {
if (presence[i] != 0) {
res[index] = i;
index++;
}
}
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + ", ");
}
}
I know for sure this can improved significantly , but you may use this as a starting point.
Integer.MAX_VALUE?
We can remove duplicates from the array using the code below without using any collections or streams. Have done it by taking the help of String class. Also the order will be preserved
// Input Array
int a[] = {1, 9, 55, 1, 8, 9, 77, 2, 5, 54, 7, 10, 11};
String s = "";
for (int i = 0; i < a.length; i++) {
String s1 = String.valueOf(a[i]);
if (!s.startsWith(s1 + " ") && !s.contains(" " + s1 + " ")) {
s = s.concat(s1 + " ");
}
}
System.out.println(s);
// output: 1 9 55 8 77 2 5 54 7 10 11
