Fairer Algorithmus, gemischtes Array
Dies ist eine Frage, die mir vor ein paar Tagen während eines Interviews begegnet ist. Als ich diese Frage sah, dachte ich zuerst an das Mischverfahren:
Methode Eins: Prinzip des Mischverfahrens
Implementieren Sie nun in der Shuffle-Methode in der Collections-Klasse im Paket java.util manuell den folgenden Code wie folgt:
package test.ms;import java.util.Random;public class Redistribute2 {public static void main(String[] args) {//define the array int[] s = {1,5,4,3,6,9, 8,7,0,8,5,6,7,2};// vor der Neuverteilung OutputSystem.out.println("before redistribute:");for(int i = 0; i<s.length; i++){System.out.print(s[i]+" ");}// rufe die Methode shuffle(s,new Random());System.out.println();// nach der Neuverteilung von OutputSystem.out auf. println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}} // unter Verwendung des Zufalls den Zufall erhalten numberpublic static void shuffle(int[] array, Random random){for(int i = array.length; i >= 1; i--){swap(array,i-1,random.nextInt(i));}}// der Zwei-Zahlen-Swap im Arraypublic static void swap(int[] array, int i , int j){ int temp = array[i];array[i] = array[j];array[j] = temp; }}
Die Swap-Methode wird verwendet, um zwei Zahlen im Array auszutauschen, und die Shuffle-Methode wird zum Austausch basierend auf Zufallszahlen verwendet, die von einer Zufallsquelle generiert werden.
Die Ausgabe ist wie folgt:
vor der Neuverteilung:1 5 4 3 6 9 8 7 0 8 5 6 7 2 nach der Neuverteilung:9 8 7 8 0 6 1 6 5 5 2 3 7 4
Methode 2: Generieren Sie einen zufälligen Indexaustausch
Diese Methode nutzt die Eigenschaften der Set-Sammlung: Die Daten in der Set-Sammlung werden nicht wiederholt, ein Index des Arrays wird generiert und Daten werden basierend auf dem generierten Index ausgetauscht.
Dies wird wie folgt erreicht:
package test.ms;import java.util.Iterator;import java.util.LinkedHashSet;import java.util.Random;import java.util.Set;public class Redistribute {public static void main(String[] args) {int[ ] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2};redistribute(s);}public static void redistribute(int[] s){Random random = new Random();Set<Integer> set = new LinkedHashSet<Integer>();// den Index neu verteilenwhile(true){int t =random.nextInt(s.length) ;set.add(t);if(set.size()== s.length)break;}System.out.println("before redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}System.out.println();System.out.println("redistribute the index");System .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++;}// das Ergebnis ausgeben;System.out.println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(out[i]+" ");}}}Diese Methode generiert zunächst einen Index und führt dann den Datenaustausch basierend auf dem neuen Index durch. Der gesamte Code ist in der Hauptmethode geschrieben, was nicht sehr gut ist.
Die generierten Ergebnisse lauten wie folgt:
Vor der Neuverteilung:1 5 4 3 6 9 8 7 0 8 5 6 7 2 Verteilen Sie den Index [6, 2, 9, 1, 10, 5, 11, 4, 12, 3, 7, 8, 0, 13] danach neu umverteilen:8 4 8 5 5 9 6 6 7 3 7 0 1 2
Bezüglich der Generierung von Zufallszahlen wird die Toolklasse zur Generierung von Zufallszahlen in der Java-Klasse verwendet. Diese Zufallsklasse muss separat untersucht werden.