公平なアルゴリズム、シャッフル配列
これは、数日前のインタビュー中に私が遭遇した質問です。この質問を見たとき、私は最初にシャッフル手順について考えました。
方法 1: シャッフル手順の原則
java.util パッケージの Collections クラスの shuffle メソッドで、次のようにコードを手動で実装します。
package test.ms;import java.util.Random;public class Redistribute2 {public static void main(String[] args) {//配列 int[] s = {1,5,4,3,6,9, を定義します。 8,7,0,8,5,6,7,2};// 再配布前 OutputSystem.out.println("before redistribute:");for(int i = 0; i<s.length; i++){System.out.print(s[i]+" ");}//outputSystem.out を再配布した後、メソッド shuffle(s,new Random());System.out.println();// を呼び出します。 println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}} // ランダムを使用してランダムを取得します数値パブリック静的無効shuffle(int[] array, Random random){for(int i = array.length; i >= 1; i--){swap(array,i-1,random.nextInt(i));}}//配列内の 2 つの数値の交換public static void swap(int[] array, int i , int j){ int temp = array[i];array[i] = array[j];array[j] = temp; }}
スワップ方式は配列内の 2 つの数値を交換するために使用され、シャッフル方式はランダム ソースによって生成された乱数に基づいて交換するために使用されます。
出力は次のとおりです。
再配布前:1 5 4 3 6 9 8 7 0 8 5 6 7 2 再配布後:9 8 7 8 0 6 1 6 5 5 2 3 7 4
方法 2: ランダムなインデックス交換を生成する
このメソッドは、Set コレクションのデータが繰り返されず、配列のインデックスを生成し、生成されたインデックスに基づいてデータを交換するという Set コレクションの特性を利用します。
これは次のようにして実現されます。
パッケージ 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>();// インデックスを再配布しますwhile(true){int t =random.nextInt(s.length) ;set.add(t);if(set.size()== s.length)break;}System.out.println("再配布前:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}System.out.println();System.out.println("インデックスを再配布する"); .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++;}// 結果を出力;System.out.println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(out[i]+" ");}}}このメソッドは、最初にインデックスを生成し、次に新しいインデックスに基づいてデータ交換を実行します。コードはすべて main メソッドで記述されており、あまり優れていません。
生成された結果は次のとおりです。
再配布前:1 5 4 3 6 9 8 7 0 8 5 6 7 2 インデックス [6、2、9、1、10、5、11、4、12、3、7、8、0、13] を再配布後再配布:8 4 8 5 5 9 6 6 7 3 7 0 1 2
乱数の生成については、Javaクラスの乱数生成用のツールクラスを使用します。この乱数クラスは別途検討する必要があります。