How to remove duplicate elements from a given array in java without using collections
This is the next step from the Element Distinctness Issue , which is discussed in detail in this thread: Find duplicates in an array , including the lower bounds of the problem (can't be better than O(nlogn)
no hash set involved).
If you don't want to use a hash set to check all the elements you've already seen, your best bet is to sort the array and then iterate over it - all the repeated 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 the simpler variant above can also do this in-place without creating a new array.
This solution is O(nlogn)
and therefore optimal. You can implement your own sorting algorithm (it's pretty easy) if you don't want to use Arrays.sort()
.
Another related thread that asks a similar question with an additional restriction: Removing duplicates from an array without breaking the order of the elements without using sets
source to share
Got a very good solution for this question: it works great. For those still looking for an answer to this question, you can use this below code snippet.
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]);
}
}
}
source to share
public int[] removeDuplicates(int[] arr) {
int[] res = new int[arr.length];
int index = 0;
for (int num : arr) {
if (res.indexOf(num) == -1)
res[index++] = num;
}
return res;
}
This is a suboptimal solution, however it does not require sorting the array. I create a new array, iterate over the elements in the original, and add the elements to the new array if they don't already exist.
source to share
public static int[] removeDuplicates(int[] input){
int j = 0;
int i = 1;
//return if the array length is less than 2
if(input.length < 2){
return input;
}
while(i < input.length){
if(input[i] == input[j]){
i++;
}else{
input[++j] = input[i++];
}
}
int[] output = new int[j+1];
for(int k=0; k<output.length; k++){
output[k] = input[k];
}
return output;
}
Source: http://java2novice.com/java-interview-programs/remove-duplicates-sorted-array/
source to share
package practice1;
import java.util.Scanner;
public class RemoveArrayDuplicatesElements {
public static void main(String[] args) {
int i, j, k, size,same = 0;
System.out.println("\nEnter array size : ");
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
size = sc.nextInt();
int[] arr = new int[size+1];
System.out.println("\nAccept Numbers : ");
for (i = 0; i < size; i++)
arr[i] = sc.nextInt();
System.out.println("\nArray with Unique list : ");
for (i = 0; i < size; i++) {
for (j = i + 1; j < size;) {
if (arr[j] == arr[i]) {
same++;
for (k = j; k < size; k++) {
arr[k] = arr[k + 1];
}
size--;
} else
j++;
}
}
for (int g = 0; g < arr.length; g++) {
System.out.println(arr[g]);
}
}
}
source to share
public class UniqueElementinAnArray
{
public static void main(String[] args)
{
int[] a = {10,10,10,10,10,100};
int[] output = new int[a.length];
int count = 0;
int num = 0;
//Iterate over an array
for(int i=0; i<a.length; i++)
{
num=a[i];
boolean flag = check(output,num);
if(flag==false)
{
output[count]=num;
++count;
}
}
//print the all the elements from an array except zero (0)
for (int i : output)
{
if(i!=0 )
System.out.print(i+" ");
}
}
/***
* If a next number from an array is already exists in unique array then return true else false
* @param arr Unique number array. Initially this array is an empty.
* @param num Number to be search in unique array. Whether it is duplicate or unique.
* @return true: If a number is already exists in an array else false
*/
public static boolean check(int[] arr, int num)
{
boolean flag = false;
for(int i=0;i<arr.length; i++)
{
if(arr[i]==num)
{
flag = true;
break;
}
}
return flag;
}
}
source to share
package com.array;
import java.util.*;
class RemoveDuplicatesInArray{
public static void main(String[] args) {
Integer[] array = new Integer[10];
array[0] = 1;
array[1] = 2;
array[2] = 3;
array[3] = 3;
array[4] = 3;
array[5] = 3;
array[6] = 7;
array[7] = 7;
array[8] = 9;
array[9] = 9;
removeDuplicatesFromArray(array);
}
private static void removeDuplicatesFromArray(Integer[] array){
StringBuffer stringBuffer = new StringBuffer();
String arrayString = Arrays.toString(array);
for(int index =0 ; index <= arrayString.length(); index++){
try{
int number = Integer.parseInt(arrayString.charAt(index)+"");
if(!stringBuffer.toString().contains(number+"")){
if(stringBuffer.length()!=0)
stringBuffer.append(",");
stringBuffer.append(number);
}
}catch(Exception e){
}
}
String[] stringArray = stringBuffer.toString().split(",");
array = new Integer[stringArray.length];
for(int index = 0 ; index < stringArray.length ; index++){
array[index] = Integer.parseInt(stringArray[index]);
}
System.out.println(Arrays.toString(array));
}
}
source to share