Tiga Trik Mencari Elemen Ganda dalam Array dengan Java

Ada banyak solusi untuk mencari elemen ganda dalam suatu array di Java dan artikel ini akan menunjukkan tiga diantaranya. Solusi yang digunakan pada artikel ini bersifat umum dan dapat diaplikasikan ke semua jenis array (array String, integer, atau objek). Salah satu cara yang paling banyak digunakan adalah dengan menggunakan metode brute force yang membandingkan tiap elemen array satu sama lain. Solusi ini memiliki kompleksitas waktu O(n^2) dan hanya digunakan untuk keperluan pendidikan. Solusi ini tidak perlu digunakan project sungguhan.

Metode standar untuk mencari elemen ganda di dalam suatu array adalah menggunakan struktur data HashSet. Kalau pembaca ingat, tipe data abstrak Set tidak mengijinkan adanya duplikat. Pembaca dapat menggunakan kelebihan tipe data ini untuk menyaring elemen ganda. Solusi ini memiliki kompleksitas waktu O(n) karena kita hanya perlu menyisir array sekali. Solusi ini juga memiliki kompleksitas ruang sebesar O(n) karena akan menyimpan elemen yang unik dalam array tersebut.

Solusi yang ketiga untuk mencari elemen ganda dalam suatu array mirip dengan solusi yang kedua namun menggunakan struktur data hash table. Solusi ini sangat baik karena dapat diperluas fungsinya untuk menghitung jumlah duplikat. Dengan solusi ini kita akan menyisir tiap elemen dalam array dan membuat map untuk menyimpan elemen array dan jumlahnya. Setelah table dibuat, kita dapat menyisir hash table tersebut dan mencetak semua elemen, elemen yang memiliki jumlah lebih dari satu adalah elemen ganda.

Solusi 1:

Solusi kita yang pertama sangat sederhana. Yang perlu kita lakukan ialah menyusuri sebuah array dan membandingkan tiap elemen ke elemen-elemen yang lain. Kita juga perlu memastikan bahwa kita membandinkan elemen dengan dirinya sendiri dengan membandingkan i != jsebelum menghitung duplikasinya. Karena kita membandingkan tiap elemen dengen elemen yang lain dalam array, maka solusi ini memiliki kompleksitas waktu quadratic (O(n^2)). Solusi ini memiliki kompleksitas waktu yang paling jelek.

for (int i = 0; i < names.length; i++) { 
  for (int j = i + 1 ; j < names.length; j++) {
     if (names[i].equals(names[j])) { 
          // aksi untuk elemen ganda
     } 
  }
}

Solusi 2:

Solusi kedua bahkan lebih mudah. Yang perlu diketahui hanyalah pengetahuan bahwa struktur data Set tidak mengijinkan duplikat di Java. Artinya jika kita menambahkan elemen yang sama ke dalam suatu Set, maka akan terjadi error. Di Java kita dapat menggunakan kelas HashSet untuk menjalankan solusi ini.

Yang perlu kita lakukan adalah menyusuri elemen array dan memasukan tiap elemen ke dalam HashSet menggunakan metode add() dan memeriksa nilai kembaliannya. Jika add() mengembalikan nilai false artinya elemen tersebut tidak diterima, dengan kata lain elemen yang tidak diterima tersebut merupakan elemen duplikat. Ini dia potongan kode yang dapat digunakan.

for (String name : names) {
    if (set.add(name) == false) {
        // aksi untuk elemen ganda
    }
}

Kompleksitas waktu solusi ini adalah O(n) karena kita hanya perlu menyusuri array sebanyak satu kali, namun solusi ini juga memiliki kompleksitas ruang O(n) karena menggunakan struktur data HashSet yang hanya berisi elemen yang unik. Jadi jika sebuah array memiliki elemen sebanyak 1 juta, kondisi terburuk yang mungkin dapat ditemui adalah kita perlu menyimpan 1 juta elemen tersebut kedalam HashSet.

Solusi 3

Solusi yang ketiga mengambil kelebihan dari struktur data lain yaitu hash table. Semua yang perlu kita lakukan adalah menyusuri array menggunakan enhanced for loop dan mengisi tiap elemen dan jumlahnya ke dalam hash table. Jika dapat menggunakan kelas HashMap di Java untuk menyelesakannya. Untuk membuat table, kita perlu memerikasa apakah hashtable memiliki elemen tersebut atau tidak, jika terdapat elemen yang sama maka jumlah elemen tersebut ditambahkan namun jika tidak ada elemen yang sama maka elemen tersebut ditambahkan dengan jumlah satu. Setelah table selesai dibuat, kita dapat menyusurinya dan mencetak semua jumlahnya untuk melihat yang mana yang memiliki nilai lebih dari satu. Solusi ini merupakan solusi yang sangat baik karena kita dapat memeperluasnya untuk menentukan jumlah duplikat yang ada.

// membuat hashtable
for (String name : names) {
    Integer count = nameAndCount.get(name);
    if (count == null) {
        nameAndCount.put(name, 1);
    } else {
        nameAndCount.put(name, ++count);
    }
}
// mencetak elemen duplikat
Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet();
for (Entry<String, Integer> entry : entrySet) {
if (entry.getValue() > 1) {
System.out.printf("elemen ganda '%s' dengan jumlah '%d'", entry.getKey(), entry.getValue());
}
}

Kompleksitas wkatu untuk solusi ini adalah O(2n) karena kita menyusuri array tersebut dua kali dan kompleksitas ruangnya sama dengan solusi sebelumnya yaitu O(n). Kasus terburuk yang dapat ditemui yaitu kita memerlukan sebuah hash table yang sama besarnya dengan array sumber.

Program Pencari Elemen Ganda dalam Array

Berikut ini program utuh untuk mencari elemen ganda dalam array dengan tiga metode yang telah kita bahas sebelumnya. Contoh program ini dapat dijalankan secara langsung lewat command line atau menggunakan IDE (Eclipse, Netbeans, IntelliJ). Pastikan nama file sama dengan nama kelas publik (contoh ini kelas publinya adalah DuplicatesInArray, maka nama filenya DuplicatesInArray.java). Pembaca dapat melakukan sedikit latihan jika mau. Program di bawah ini dapat di-refactor dengan memisahkan kode pencari elemen ganda ke dalam method yang baru. Hal ini dapat dilakukan dengan menggunakan fitur extract IDE modern seperti Eclipse dan Netbeans. Latihan ini dapat melatih kita melakukan refactoring yang dapat digunakan nantinya untuk menulis tes JUnit. Dua kegiatan ini merupakan atribut penting seorang programmer profesional.

import java.util.HashMap;
import java.util.HashSet; 
import java.util.Map; 
import java.util.Map.Entry; 
import java.util.Set; 
/**

Java Program to find duplicate elements in an array. There are two straight
forward solution of this problem first, brute force way and second by using
HashSet data structure. A third solution, similar to second one is by using
hash table data structure e.g. HashMap to store count of each element and
print element with count 1.

@author java67
*/

public class DuplicatesInArray{
public static void main(String args[]) {
String[] names = { "Java", "JavaScript", "Python", "C", "Ruby", "Java" };
	// First solution : finding duplicates using brute force method 
	System.out.println("Duplicate elements in array using brute force method"); 
	for (int i = 0; i < names.length; i++) { 
		for (int j = i + 1; j < names.length; j++) { 
			if (names[i].equals(names[j]) ) { 
				System.out.println("found a duplicate in array : " + names[i]);			
			}
		} 
	}

	// Second solution : use HashSet data structure to find duplicates 
	System.out.println("Duplicate elements from array using HashSet data structure"); 
	Set<String> store = new HashSet<>(); 
	for (String name : names) { 
		if (store.add(name) == false) { 
			System.out.println("found a duplicate element in array : " + name); 
		} 
	}
	
	// Third solution : using Hash table data structure to find duplicates 
	System.out.println("Duplicate elements from array using hash table"); 
	Map<String, Integer> nameAndCount = new HashMap<>(); 

	// build hash table with count 
	for (String name : names) { 
		Integer count = nameAndCount.get(name); 
		if (count == null) { 
			nameAndCount.put(name, 1); 
		} else { 
			nameAndCount.put(name, ++count); 
		} 
	} 

	// Print duplicate elements from array in Java 
	Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet(); 
	for (Entry<String, Integer> entry : entrySet) { 
		if (entry.getValue() > 1) { 
			System.out.println("Duplicate element from array : " + entry.getKey()); 
		} 
	}
}

}

Dari output di atas kita dapat melihat bahwa elemen ganda dalam array String, “Java”, dapat ditemukan oleh ketiga solusi yang kita bahas.

Diterjemahkan dengan penambahan dari artikel berjudul "3 Ways to Find Duplicate Elements in Array Java" atas ijin dari Javin Paul.