Fair algorithm, shuffled array
This is a question I encountered during an interview a few days ago. When I saw this question, I first thought of the shuffling procedure:
Method One: Principle of Shuffling Procedure
In the shuffle method in the Collections class in the java.util package, now manually implement the following code as follows:
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};// before redistribute outputSystem.out.println("before redistribute:");for(int i = 0; i<s.length; i++){System.out.print(s[i]+" ");}// invoke the method shuffle(s,new Random());System.out.println();// after redistribute outputSystem.out. println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}} // using the random get the random numberpublic static void shuffle(int[] array, Random random){for(int i = array.length; i >= 1; i--){swap(array,i-1,random.nextInt(i));}}// the two number swap in the arraypublic static void swap(int[] array, int i , int j){ int temp = array[i];array[i] = array[j];array[j] = temp; }}
The swap method is used to exchange two numbers in the array, and the shuffle method is used to exchange based on random numbers generated by a random source.
The output is as follows:
before redistribute:1 5 4 3 6 9 8 7 0 8 5 6 7 2 after redistribute:9 8 7 8 0 6 1 6 5 5 2 3 7 4
Method 2: Generate random index exchange
This method takes advantage of the characteristics of the Set collection: the data in the Set collection is not repeated, generates an index of the array, and exchanges data based on the generated index.
This is achieved as follows:
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>();// redistribute the indexwhile(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++;}// out the result;System.out.println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(out[i]+" ");}}}This method first generates an index, and then performs data exchange based on the new index. The code is all written in the main method, which is not very good.
The generated results are as follows:
before redistribute:1 5 4 3 6 9 8 7 0 8 5 6 7 2 redistribute the index [6, 2, 9, 1, 10, 5, 11, 4, 12, 3, 7, 8, 0, 13]after redistribute:8 4 8 5 5 9 6 6 7 3 7 0 1 2
Regarding the generation of random numbers, the tool class for generating random numbers in the Java class is used. This random class needs to be studied separately.