CODEWITHSUNDEEP
java
Abhilash28
Abhilash28

Reputation: 645

Removing the duplicates from an array without disturbing the order of elements without using Sets

I need a java code which can remove the duplicates from an array without changing the order of elements and without using Sets or the sort techniques.

eg: If input array is {23,1,5,4,2,23,6,2,4} Then output should be {23,1,5,4,2,6}

Upvotes: 0

Views: 3036

Answers (6)

stefo0O0o
stefo0O0o

Reputation: 119

If you just need to print the unique elements without modifying the array, you can do it with this alternative solution. Sort the array with O(n log n) (merge sort e.g.) and run through the array O(n) to print only elements that have their adjacent element different, that is:

if( arr[i] != arr[i + 1]) {
  print(arr[i]);
}

Cheers!

Upvotes: 0

OldCurmudgeon
OldCurmudgeon

Reputation: 65803

There's several options - some more efficient than others:

/**
 * Brute force approach - very inefficient.
 *
 * Finds each duplicate and removes it.
 */
private int[] removeDupesUsingNoExtraMemory(int[] a) {
    int length = a.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            if (a[i] == a[j]) {
                // No point copying if this is the last one.
                if (j < length - 1) {
                    // Remove a[j].
                    System.arraycopy(a, j + 1, a, j, length - j - 1);
                }
                length -= 1;
            }
        }
    }
    // Actually it does use extra memory but only to trim the array because Java cannot slice arrays.
    return Arrays.copyOf(a, length);
}

/**
 * A bit more efficient.
 *
 * Copies only non-duplicate ones.
 */
private int[] removeDupesDifferently(int[] a) {
    int length = a.length;
    // Copying to the end backwards.
    int to = length - 1;
    // Copy backwards so we remove the second duplicate - not the first.
    for (int i = length - 1; i >= 0; i--) {
        boolean duplicate = false;
        for (int j = 0; j < i && !duplicate; j++) {
            duplicate |= a[i] == a[j];
        }
        if (!duplicate) {
            a[to--] = a[i];
        }
    }
    return Arrays.copyOfRange(a, to + 1, a.length);
}

/**
 * Most efficient - but uses a `Set`.
 *
 * Builds a `Set` of `seen` values so we don't copy duplicates.
 */
private int[] removeDupesUsingASet(int[] a) {
    int to = 0;
    Set<Integer> seen = new HashSet<>();
    for (int i = 0; i < a.length - 1; i++) {
        // Seen it before?
        if (!seen.contains(a[i])) {
            a[to++] = a[i];
            // Seen that one - don't want to see it again.
            seen.add(a[i]);
        }
    }
    return Arrays.copyOf(a, to);
}

public void test() {
    System.out.println("removeDupesUsingNoExtraMemory = " + Arrays.toString(removeDupesUsingNoExtraMemory(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4})));
    System.out.println("removeDupesDifferently = " + Arrays.toString(removeDupesDifferently(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4})));
    System.out.println("removeDupesUsingASet = " + Arrays.toString(removeDupesUsingASet(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4})));
}

Upvotes: 0

amit
amit

Reputation: 178421

You can do it in O(n^2) time with O(1) extra space.

public static int[] noSpaceElementDistinctness(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n;i++) {
        boolean exists = false;
        for (int j = 0; j < i; j++) {
            if (arr[i] == arr[j]) {
                exists = true;
                break;
            }
        }
        if (exists) {
            for (int j = i+1; j<n; j++)
                arr[j-1] = arr[j];
        n--;
        i--; //to iterate the next element, which is now at index i, not i+1.
        }
    }
    for (int i = n; i < arr.length; i++) arr[i] = Integer.MIN_VALUE; //indicates no value
    return arr;

}

As a side note, the element distinctness problem is not that trivial to solve efficiently as it might seem from first glance, and it is one problem with strict lower bound of what you can do to solve it efficiently. This thread discusses it.

Upvotes: 3

Sambit Jaysingh
Sambit Jaysingh

Reputation: 1

    int arr[] = {23,1,5,4,2,6} ;
    List<Integer> list = new ArrayList<Integer>();
    for(int i = 0; i<arr.length; i++) {
        if (!list.contains(arr[i])) {
            list.add(arr[i]);
        }
    }

    Iterator it = list.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }

Upvotes: 0

assylias
assylias

Reputation: 328598

If you use Java 8 a simple way would be:

int[] array = {23, 1, 5, 4, 2, 23, 6, 2, 4};
int[] noDupes = IntStream.of(array).distinct().toArray();
System.out.println(Arrays.toString(noDupes)); // [23, 1, 5, 4, 2, 6]

Upvotes: 1

Danielson
Danielson

Reputation: 2696

Create a new ArrayList(). Loop over old list and copy the value to new unless it is already in it.

The order will be changed because you will not copy all...

Upvotes: 0

Related Questions