Solution: Find Duplicates in Array
Let's look at the various solutions for finding the duplicates in an array.
Solution #1: Brute force
Press + to interact
class Duplicates {public static ArrayList < Integer > findDuplicates(int arr[]) {int arrSize = arr.length;ArrayList < Integer > duplicates = new ArrayList < Integer > ();for (int i = 0; i < arrSize; i++) {for (int j = i + 1; j < arrSize; j++) {if (arr[i] == arr[j] && i != j)duplicates.add(arr[i]);}}return duplicates;}public static void main(String[] args) {int arr[] = {7,5,4,3,5,11,7,11,3,11};ArrayList < Integer > dupes = findDuplicates(arr);System.out.println("Duplicates in " + Arrays.toString(arr) + " are " + dupes);int arr1[] = {6,5,17,17};dupes = findDuplicates(arr1);System.out.println("Duplicates in " + Arrays.toString(arr1) + " are " + dupes);}}
This solution iterates over the input array for each given element, starting from the element after the given element, and checks if another element is equal to it or not (lines 6-8). If it is equal, then it is added to the output list
—duplicates
(line 9). However, when you have more than 2 copies of any given element, the element is added to the ArrayList
as many times as it is present. This does not look great, as shown in the case of the array on line 25 (11 occurs thrice in the output). We can check if the element has already been counted, as in solution # 2.
Time complexity
The array is iterated once for each element present so the time complexity is in ...
Access this course and 1400+ top-rated courses and projects.