Algoritmo justo, array embaralhado
Esta é uma pergunta que encontrei durante uma entrevista há alguns dias. Quando vi esta pergunta, pensei pela primeira vez no procedimento de embaralhamento:
Método Um: Princípio do Procedimento de Embaralhamento
No método shuffle na classe Collections no pacote java.util, agora implemente manualmente o seguinte código:
package test.ms;import java.util.Random;public class Redistribute2 {public static void main(String[] args) {//defina o array int[] s = {1,5,4,3,6,9, 8,7,0,8,5,6,7,2};// antes de redistribuir outputSystem.out.println("antes de redistribuir:");for(int i = 0; i<s.length; i++){System.out.print(s[i]+" ");}// invoca o método shuffle(s,new Random());System.out.println();// após redistribuir outputSystem.out. println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}} // usando o aleatório obtém o aleatório número público estático vazio shuffle(int[] array, Random random){for(int i = array.length; i >= 1; i--){swap(array,i-1,random.nextInt(i));}}// a troca de dois números no arraypublic static void swap(int[] array, int i , int j){ int temp = array[i];array[i] = array[j];array[j] = temp; }}
O método swap é usado para trocar dois números na matriz, e o método shuffle é usado para trocar com base em números aleatórios gerados por uma fonte aleatória.
A saída é a seguinte:
antes de redistribuir:1 5 4 3 6 9 8 7 0 8 5 6 7 2 depois de redistribuir:9 8 7 8 0 6 1 6 5 5 2 3 7 4
Método 2: gerar troca aleatória de índices
Este método aproveita as características da coleção Set: os dados da coleção Set não se repetem, gera um índice do array e troca dados com base no índice gerado.
Isto é conseguido da seguinte forma:
pacote test.ms;importar java.util.Iterator;importar java.util.LinkedHashSet;importar java.util.Random;importar java.util.Set;classe pública Redistribuir {public static void main(String[] args) {int[ ] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2};redistribuir(s);}public static void redistribute(int[] s){Random random = new Random();Set<Integer> set = new LinkedHashSet<Integer>();// redistribui o indexwhile(true){int t =random.nextInt(s.length) ;set.add(t);if(set.size()== s.length)break;}System.out.println("antes de redistribuir:");for(int i = 0 ; i<s.length; i++){System.out.print(s[i]+" ");}System.out.println();System.out.println("redistribuir o índice ");System. .out.println(set);int [] out = new int[s.length];int contagem = 0;for(Iterator<Integer> iterator = set.iterator(); iterator.hasNext();){out[count] = s[iterator.next()];count++;}// saída do resultado;System.out.println("after redistribute:");for(int i = 0 ; i<s.comprimento; i++){System.out.print(out[i]+" ");}}}Este método primeiro gera um índice e depois realiza a troca de dados com base no novo índice. O código é todo escrito no método principal, o que não é muito bom.
Os resultados gerados são os seguintes:
antes de redistribuir:1 5 4 3 6 9 8 7 0 8 5 6 7 2 redistribuir o índice [6, 2, 9, 1, 10, 5, 11, 4, 12, 3, 7, 8, 0, 13]depois redistribuir:8 4 8 5 5 9 6 6 7 3 7 0 1 2
Em relação à geração de números aleatórios, é utilizada a classe de ferramenta para geração de números aleatórios da classe Java. Essa classe aleatória precisa ser estudada separadamente.