Algoritma yang adil, susunan yang diacak
Ini adalah pertanyaan yang saya temui saat wawancara beberapa hari yang lalu. Ketika saya melihat pertanyaan ini, saya pertama kali memikirkan prosedur pengocokan:
Metode Satu: Prinsip Prosedur Pengocokan
Pada metode shuffle di kelas Collections pada paket java.util, sekarang implementasikan kode berikut secara manual sebagai berikut:
paket test.ms;import java.util.Random;public class Redistribute2 {public static void main(String[] args) {//definisikan array int[] s = {1,5,4,3,6,9, 8,7,0,8,5,6,7,2};// sebelum mendistribusikan ulang outputSystem.out.println("sebelum mendistribusikan ulang:");for(int i = 0; i<s.length; i++){System.out.print(s[i]+" ");}// memanggil metode shuffle(s,new Random());System.out.println();// setelah mendistribusikan ulang outputSystem.out. println("setelah mendistribusikan ulang:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}} // menggunakan acak, dapatkan acak kekosongan statis nomor publik shuffle(int[] array, Acak acak){for(int i = array.length; i >= 1; i--){swap(array,i-1,random.nextInt(i));}}// pertukaran dua angka dalam arraypublic static void swap(int[] array, int i , int j){ int temp = array[i];array[i] = array[j];array[j] = temp; }}
Metode swap digunakan untuk menukar dua angka dalam array, dan metode shuffle digunakan untuk menukar berdasarkan angka acak yang dihasilkan oleh sumber acak.
Outputnya adalah sebagai berikut:
sebelum didistribusikan kembali:1 5 4 3 6 9 8 7 0 8 5 6 7 2 setelah didistribusikan kembali:9 8 7 8 0 6 1 6 5 5 2 3 7 4
Metode 2: Hasilkan pertukaran indeks acak
Metode ini memanfaatkan karakteristik kumpulan Kumpulan: data dalam kumpulan Kumpulan tidak terulang, menghasilkan indeks array, dan menukar data berdasarkan indeks yang dihasilkan.
Hal ini dicapai sebagai berikut:
paket test.ms;impor java.util.Iterator;impor java.util.LinkedHashSet;impor java.util.Random;impor java.util.Set;kelas publik Mendistribusikan ulang {public static void main(String[] args) {int[ ] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2};mendistribusikan ulang;}kekosongan statis publik redistribusi(int[] s){Random random = new Random();Set<Integer> set = new LinkedHashSet<Integer>();// mendistribusikan kembali indeks while(true){int t =random.nextInt(s.length) ;set.add(t);if(set.size()== s.length)break;}System.out.println("sebelum mendistribusikan ulang:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}System.out.println();System.out.println("mendistribusikan ulang indeks ");Sistem .out.println(set);int [] out = new int[s.length];int count = 0;for(Iterator<Integer> iterator = set.iterator(); iterator.hasNext();){out[count] = s[iterator.next()];count++;}// keluar hasilnya;System.out.println("after redistribusi:");for(int i = 0 ; i<s.panjang; i++){Sistem.keluar.cetak(keluar[i]+" ");}}}Metode ini pertama-tama menghasilkan indeks, dan kemudian melakukan pertukaran data berdasarkan indeks baru. Semua kode ditulis dalam metode utama, yang tidak terlalu bagus.
Hasil yang dihasilkan adalah sebagai berikut:
sebelum mendistribusikan ulang:1 5 4 3 6 9 8 7 0 8 5 6 7 2 mendistribusikan ulang indeks [6, 2, 9, 1, 10, 5, 11, 4, 12, 3, 7, 8, 0, 13]setelah mendistribusikan kembali:8 4 8 5 5 9 6 6 7 3 7 0 1 2
Mengenai pembangkitan bilangan acak, kelas alat untuk menghasilkan bilangan acak pada kelas Java digunakan. Kelas acak ini perlu dipelajari secara terpisah.