How can I remove duplicate elements from a given array in java without using collections

Question

I have an array elements like this:

int arr[] = {1,1,2,2,3,3,4,4};

I want to remove the duplicate elements from. Searched on the internet and came to know about ArrayUtil class. Could you please help me by telling it's usage - that's how can I get an array like this in output:

arr[] = {1,2,3,4};

Answer 1

This is the next step from Element Distinctness Problem, which is discussed thoroughly in this thread: Find duplicates in an array, including lower bounds for the problem (cannot do better than O(nlogn) without a hash set involved).

If you are unwilling to use a hash-set to check out all the elements you have already seen, your best bet is to sort the array, and then iterate it - all duplicate elements will be adjacent to each other.

public static int[] justUniques(int[] arr) { 
    if (arr == null || arr.length == 0) return arr;
    Arrays.sort(arr);
    int n = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i-1]) n++;
    }
    int[] res = new int[n];
    res[0] = arr[0];
    n = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i-1]) res[n++] = arr[i];
    }
    return res;

}

Note that a simple variation of the above can also do it in-place, without creating a new array.

This solution is O(nlogn), and thus is optimal. You can implement your own sorting algorithm (it's fairly easy) if you are unwilling to use the Arrays.sort() one.

Another related thread that asks similar question with an additional restriction: Removing the duplicates from an array without disturbing the order of elements without using Sets

Answer 2

Got a very Good Solution for this question : and it works perfectly . For those who are still searching answer for this question , you can use this below piece of code.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class DuplicatesRemove {

public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    System.out.print("Enter the array size :");
    int size = Integer.parseInt(br.readLine());

    int[] arr = new int[size];

    // Creating the array
    for (int i = 0; i < size; i++) {
        System.out.print("Enter the element arr[" + i + "] = ");
        arr[i] = Integer.parseInt(br.readLine());
        System.out.println();
    }

    // displaying the array - it may contain elements in unsorted manner
    System.out.println("Before Sorting :");
    for (int i = 0; i < size; i++) {
        System.out.println("Element arr[" + i + "] = " + arr[i]);
    }
    System.out
            .println("*****************************************************");

    // Logic for sorting the elements in the array
    for (int i = 0; i < size; i++) {
        for (int j = 1; j < size - i; j++) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }

    // Printing the sorted elements - it may contain duplicate elements
    System.out.println("After Sorting :");
    for (int i = 0; i < size; i++) {
        System.out.println("Element arr[" + i + "] = " + arr[i]);
    }

    System.out
            .println("*****************************************************");
    // Logic for removing the duplicate elements
    int compare = 0;
    arr[compare] = arr[0];

    for (int i = 1; i < size; i++) {
        if (arr[compare] != arr[i]) {
            compare++;
            arr[compare] = arr[i];
        }
    }

    System.out.println("Array After removing duplicate elements is :");
    for (int i = 0; i <= compare; i++) {
        System.out.println("Element arr[" + i + "] = " + arr[i]);
      }
   }
}