Duplicate program in java

Remove Duplicates From Array in Java

An array can contain duplicate elements, and the array may be sorted or unsorted. Let us see different ways to remove duplicates from a given array in Java programming language.

Sorted array = ;
After removing the duplicates from array = ;
Unsorted Array = ;
After removing the duplicates from array = ;

In all examples, we will use toString() method of java.util.Arrays class to display the array. The Arrays.toString() method is used to convert array to string.

Using Loops

Let us discuss how to remove duplicates from sorted and unsorted array using loops. Here, we won’t use any temporary array, we will use seperate index.

Java program to remove duplicates from sorted array

In sorted array, removing duplicate elements is easy compared to the unsorted array. In the sorted array, next element can be either equal or greater/lesser (greater if array is sorted in ascending order, else lesser). If both are equal then ignore it else perform the operation. Let us see the steps.

Procedure to develop a method to remove duplicates from sorted array
a) Take an sorted array.
b) Take a variable initializing with 0, it store count of unique elements.
c) Find index of last element, lastIndex = array-size – 1
d) Iterate array upto before the last element
e) Compare two concusetive array elements. If both are same then move on, else increase count of unique element and store that unique element at approriate index in the same array.
f) For the last element, compare it with last unique element. If both are then ignore else perfom previous operation.
g) Return the copy of unique elements.

import java.util.Arrays; public class ArrayTest < public static void main(String[] args) < // sorted array int arr[] = ; // remove duplicates int newArr[] = removeDuplicates(arr); // display both arrays System.out.println("Original array: " + Arrays.toString(arr)); System.out.println("After removing duplicates: " + Arrays.toString(newArr)); > // method to remove duplicates from sorted array public static int[] removeDuplicates(int[] arr) < int j = 0; // index without duplicates int lastIndex = arr.length-1; // loop to iterate the array (except last element) for (int i = 0; i < lastIndex; i++) < if(arr[i] != arr[i+1]) < arr[j++] = arr[i]; >> // for the last element if(arr[j] != arr[lastIndex]) arr[j++] = arr[lastIndex]; // return new copied array return Arrays.copyOf(arr, j); > >

Original array: [10, 20, 30, 40, 50, 40, 50]After removing duplicates: [10, 20, 30, 40, 50]

The time complexity of this method:- O(n)

Java program to remove duplicates from unsorted array

The above program can remove duplicates only from the sorted array, but the below program can remove duplicates from any array which can be sorted/unsorted.

import java.util.Arrays; public class ArrayTest < public static void main(String[] args) < // sorted/unsorted array int arr[] = ; // remove duplicates int newArr[] = removeDuplicates(arr); // display both arrays System.out.println("Original array: " + Arrays.toString(arr)); System.out.println("After removing duplicates: " + Arrays.toString(newArr)); > // method to remove duplicates from array public static int[] removeDuplicates(int[] arr) < int index = 1; // index without duplicates // loop to iterate the array for (int i = 1; i < arr.length; i++) < // current element int element = arr[i]; // check element is in unique for(int j=0; j// when not in unique if(j == index-1) < arr[index++] = element; // index got increased therefore use break break; >> > // return new copied array return Arrays.copyOf(arr, index); > >

Original array: [30, 50, 20, 10, 40, 20, 30, 10, 10, 40]After removing duplicates: [30, 50, 20, 10, 40]

If you are wondering that how it is performing the operations then you can use below method,

// method to remove duplicates from array public static int[] removeDuplicates(int[] arr) < System.out.println(Arrays.toString(arr)); int index = 1; // index without duplicates // loop to iterate the array for (int i = 1; i < arr.length; i++) < System.out.println("Unique elements are: " + Arrays.toString(Arrays.copyOf(arr, index))); // current element int element = arr[i]; System.out.print("Current element: " + element); // check element is in unique for(int j=0; j// when not in unique if(j == index-1) < arr[index++] = element; System.out.println(", unique"); System.out.println("Index of unique = "+index); break; >> > // return new copied array return Arrays.copyOf(arr, index); >

Remove duplicates from array in Java using Set collection

Using Java collections also we can remove the duplicate from array. The set collection can store only unique values, therefore in this program we will iterate to the array and try to insert all elements in the set collection. After inserting set will be converted to the array and it is returned to the caller method.

import java.util.Arrays; import java.util.LinkedHashSet; public class ArrayTest < public static void main(String[] args) < // sorted/unsorted array int arr[] = < 30, 50, 20, 50, 10, 20, 30, 10, 10, 40 >; // remove duplicates int newArr[] = removeDuplicates(arr); // display both arrays System.out.println("Original array: " + Arrays.toString(arr)); System.out.println("After removing duplicates: " + Arrays.toString(newArr)); > // method to remove duplicates from array public static int[] removeDuplicates(int[] arr) < LinkedHashSetset = new LinkedHashSet(); // add elements to LinkedHashSet for (int element : arr) < set.add(element); >// return array result by // converting set to array return setToArray(set); > // method to convert set to int array public static int[] setToArray(LinkedHashSet set) < int temp[] = new int[set.size()]; int i = 0; for (Integer element : set) < temp[i++] = element; >return temp; > >

Original array: [30, 50, 20, 50, 10, 20, 30, 10, 10, 40]After removing duplicates: [30, 50, 20, 10, 40]

Remove duplicates from array using Java 8 stream

We can also use stream to remove the duplicates from a given array.

import java.util.Arrays; import java.util.List; import java.util.stream.Collectors; public class ArrayTest < public static void main(String[] args) < // sorted/unsorted array Integer arr[] = < 30, 50, 20, 50, 10, 20, 30, 10, 10, 40 >; System.out.println("Original array: " + Arrays.toString(arr)); // remove duplicates removeDuplicates(arr); > // method to remove duplicates from array public static void removeDuplicates(Integer[] arr) < Listlist = Arrays.asList(arr); List listWithoutDuplicates = list.stream().distinct().collect(Collectors.toList()); // display System.out.println("After removing duplicates: " + listWithoutDuplicates); > >

Original array: [30, 50, 20, 50, 10, 20, 30, 10, 10, 40]After removing duplicates: [30, 50, 20, 10, 40]

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Источник

Tech Tutorials

Tutorials and posts about Java, Spring, Hadoop and many more. Java code examples and interview questions. Spring code examples.

Tuesday, June 1, 2021

Find Duplicate Elements in an Array Java Program

If you have to write a Java program to find duplicate elements in an array one option you have is to loop through the array taking one element at a time and then compare it with all the other elements of the array in order to find the duplicates. Though this solution works fine but the problem here is you are looping though the array twice making the time complexity of this solution O(n 2 ). Because of the double iteration program will be slow.

Another option to find duplicate elements in an array is to sort the array first and then compare the adjacent element in a loop. Since array is sorted so the repeated elements would be adjacent to each other so you don’t need an inner loop to compare current element with all the elements of the array. Thus the time complexity of this solution is O(nlogn + n). Time required for sorting is O(nlogn) and iteration of the array requires O(n) time.

To further minimize the execution time you can think of using a data structure like HashSet which will reduce the time complexity to O(n).

Since Set doesn’t allow duplicate elements trying to do that will return false. So you can have a logic where you iterate an array and try to add element to the HashSet, if adding an element to the HashSet returns false that means a duplicate element. As I said since array is iterated only once so time complexity is O(N) here but a new data structure is created, apart from array you are also creating a Set, so space complexity increases here, extra space used is O(N).

Let’s see Java program to find duplicate elements in an array using all of the approaches discussed above.

Looping through unsorted Array and comparing elements to find duplicates

Here you have an outer loop that iterates the array one element at a time and another loop that starts from the next element and iterates through all the elements of the array and compares it with the current element.

public class DuplicateArrayElement < public static void main(String[] args) < int[] numArray = ; for(int i = 0; i < numArray.length; i++)< for(int j = i + 1; j < numArray.length; j++)< if(numArray[i] == numArray[j])< System.out.println("Duplicate element found " + numArray[j]); >> > > >

Duplicate element found 2 Duplicate element found 6 Duplicate element found 19

Finding duplicate elements in a sorted Array

public class DuplicateArrayElement < public static void main(String[] args) < int[] numArray = ; // sort array Arrays.sort(numArray); for(int i = 0; i < numArray.length - 1; i++)< if(numArray[i] == numArray[i+1])< System.out.println("Duplicate element found " + numArray[i]); >> > >

Duplicate element found 1 Duplicate element found 19

Using HashSet to find duplicate elements in an array

In this solution to find duplicate elements in an array in Java, iteration of the array is done and elements of the array are added to the set.

Here thing to understand is- If set already contains the element, call to add method of the set leaves the set unchanged and returns false. So, whenever false is returned that means a duplicate element.

public class DuplicateArrayElement < public static void main(String[] args) < int[] numArray = ; Set numSet = new HashSet(); for(int num : numArray) < // If add returns false if(!numSet.add(num))< System.out.println("Duplicate element found " + num); >> > >

Duplicate element found 2 Duplicate element found 6 Duplicate element found 19

That’s all for this topic Find Duplicate Elements in an Array Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

Источник

Duplicate Elimination Java Program

Question : (Duplicate Elimination) Use a one-dimensional array to solve the following problem: Write an application that inputs five numbers, each between 10 and 100, inclusive. As each number is read, display it only if it’s not a duplicate of a number already read. Provide for the “worst case,” in which all five numbers are different. Use the smallest possible array to solve this problem. Display the complete set of unique values input after the user enters each new value.

Duplicate Elimination inputs five numbers, each between 10 and 100, inclusive

/* * Filename: DuplicateElimination.java * * Description: Exercise 7.12 - Duplicate Elimination * * @Author: Bilal Tahir Khan Meo * Website: https://codeblah.com * * ===================================================================================== */ import java.util.Scanner; import java.util.Arrays; public class DuplicateElimination < private static int[] arrValues = new int[5]; public static void main(String[] args)< Scanner sc = new Scanner(System.in); int remaining = 0; while(remaining != 5)< System.out.printf("Enter value %d/5 between 10 and 100: ", remaining + 1); int num = sc.nextInt(); // ensure input is within range if(num < 10 || num >100) continue; // print unique values if(isUnique(num)) System.out.printf("Unique value: %d\n", num); try< // add to array and increase counter arrValues[remaining++] = num; >catch(ArrayIndexOutOfBoundsException e) < System.out.println(e); >// display complete set of unique values printUnique(); > > // ensure value is unique // Arrays.binarySearch() for some reason does not work so needed this public static boolean isUnique(int num) < for(int i=0; ireturn true; > // display complete set of unique values public static void printUnique() < System.out.println("\nUnique values:\n"); // base case is always first element System.out.print(arrValues[0] + " "); // unique value storage int unique = 0; // loop through remainder for(int i=1; i0 // avoids redundant checking before array is filled if(arrValues[i] > 0)< // loop backwards checking for duplicates for(int j=i-1; j>=0; j--)< if(arrValues[i] == arrValues[j])< unique = 0; break; >else < unique = arrValues[i]; >> if(unique > 0) System.out.print(unique + " "); >else < continue; >> System.out.println(); > > 

Method 2 : Duplicate Elimination Java Program

import java.util.*; public class Test < public static void main(String[] args) < int i=0; int dizi[]=new int[100]; Scanner input=new Scanner(System.in); do< System.out.println((i+1)+" sayi="); int n=input.nextInt(); if(elemanVarmı(dizi, n)==false) < dizi[i]=n; i++; >else if(elemanVarmı(dizi,n)==true) < System.out.println("Girilen sayilar ayni"); >>while(i <5); >private static boolean elemanVarmı(int dizi[], int n) < for (int i = 0; i < dizi.length; i++) < if(dizi[i]==n) < return true; >> return false; > >

Источник