CODEWITHSUNDEEP
java
Hoang Truong
Hoang Truong

Reputation: 65

How to delete all duplicate element from an array without using any library or collection

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!

Upvotes: 1

Views: 802

Answers (4)

Vamsi
Vamsi

Reputation: 1

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

Upvotes: 0

berrur
berrur

Reputation: 125

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.

Upvotes: 0

JArgente
JArgente

Reputation: 2297

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();

Upvotes: 1

Eden Moshe
Eden Moshe

Reputation: 1147

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;

Upvotes: 1

Related Questions