ankit ankit -4 years ago 96
Java Question

Removing duplicates from array without using Util classes

Please read the question before marking it as duplicate

I have written following code to remove duplicates from array without using Util classes but now I am stuck

public class RemoveDups{
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 3, 1, 4, 52, 1, 45, };

int temp;
for (int i : a) {
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
a = removeDups(a);
for (int i : a) {
System.out.println(i);
}

}

private static int[] removeDups(int[] a) {
int[] result = new int[a.length];
int j = 0;
for (int i : a) {
if (!isExist(result, i)) {
result[j++] = i;
}
}

return result;
}

private static boolean isExist(int[] result, int i) {
for (int j : result) {
if (j == i) {
return true;
}
}
return false;
}

}


and now the output is

1
2
3
4
5
6
45
52
0
0
0
0
0
0
0
0
0
0


Here my problem is


  1. My code is not working in case of 0s

  2. I am not able to understand how sorting an array can reduce time of execution

  3. Is there any way to remove elements from array without using Util classes I know one way to remove convert array into list and then remove but for that also we need Util classes is there any way to implement by myself.


Answer Source

Since the numbers you deal with are limited to a small range you can remove duplicates by a simple "counting sort": mark the numbers you have found in a set-like data structure and then go over the data structure. An array of boolean works just fine, for less memory usage you could create a basic bitset or hash table. If n is the number of elements in the array and m is the size of the range, this algorithm will have O(n+m) complexity.

private static int[] removeDups(int[] a, int maxA) {
    boolean[] present = new boolean[maxA+1];
    int countUnique = 0;
    for (int i : a) {
        if (!present[i]) {
            countUnique++;
            present[i] = true;
        }
    }

    int[] result = new int[countUnique];
    int j = 0;
    for (int i=0; i<present.length; i++) {
        if (present[i]) result[j++] = i;
    }

    return result;
}

I am not able to understand how sorting an array can reduce time of execution

In a sorted array you can detect duplicates in a single scan, taking O(n) time. Since sorting is faster than checking each pair - O(n log n) compared to O(n²) time complexity - it would be faster to sort the array instead of using the naive algorithm.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download