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

Question

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!

Why is not possible to use a set? if the elements are comparable it should works — JArgente, Jan 11 '21 at 08:21
Aren't Set a collection? As the title said, I cannot use any Collection, including Set/HashMap — Hoang Truong, Jan 11 '21 at 08:22
Can you use a Stream? Stream is not a collection and because of this is not in collection package — JArgente, Jan 11 '21 at 08:29

score 1 · Answer 1 · answered Jan 11 '21 at 08:30

1

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;

answered Jan 11 '21 at 08:30

Eden Moshe

1,097
1
6
16

Yeah, I thought about that way too. But my teacher said it is not the most efficiently way – Hoang Truong Jan 11 '21 at 08:31
If you are looking for efficiency, without any shadow of a doubt you can use hash map – Eden Moshe Jan 11 '21 at 08:34
Aren't Hashmap a collection too? – Hoang Truong Jan 11 '21 at 08:36
Currently the efficiency is nLOg n Sorting may take nLog n, And the inner loop take o(n) – Eden Moshe Jan 11 '21 at 08:37
https://www.w3schools.com/java/java_hashmap.asp You must run on the loop once, store in the hash map as ey any value you found. If it exists in the hash map you will ignore the storage. Efficiency o (n) – Eden Moshe Jan 11 '21 at 08:39
see hashmap and collecation : https://stackoverflow.com/questions/2651819/why-doesnt-java-map-extend-collection – Eden Moshe Jan 11 '21 at 08:41

score 1 · Answer 2 · answered Jan 11 '21 at 08:37

1

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

answered Jan 11 '21 at 08:37

JArgente

2,239
1
9
11

score 0 · Answer 3 · answered Jan 11 '21 at 09:47

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.

yep, there are several limits, another one could be with an input array of negative numbers. There are a lot of assumptions with this solution, because who posted the question has not been very clear on the constraints to this problem (the only constraint was a linear time solution since sorting and removing was not efficient enough according to the poster's teacher) — berrur, Jan 11 '21 at 22:19

Vamsi · Answer 4 · 2021-01-12T06:44:46.417

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

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

4 Answers4