Честный алгоритм, перетасованный массив
С этим вопросом я столкнулся во время интервью несколько дней назад. Когда я увидел этот вопрос, я впервые подумал о процедуре перетасовки:
Метод первый: принцип процедуры перетасовки
В методе перемешивания в классе Collections пакета java.util вручную реализуйте следующий код следующим образом:
пакет test.ms;import java.util.Random;public class Redistribute2 {public static void main(String[] args) {//define массив int[] s = {1,5,4,3,6,9, 8,7,0,8,5,6,7,2};// перед перераспределением outputSystem.out.println("перед перераспределением:");for(int i = 0; i<s.length; i++){System.out.print(s[i]+" ");}// вызываем метод shuffle(s,new Random());System.out.println();// после перераспределения выводаSystem.out. 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));}}// обмен двумя числами в массиве arraypublic static void swap(int[] array, int i, int j) { int temp = array[i];array[i] = array[j];array[j] = temp; }}
Метод swap используется для обмена двумя числами в массиве, а метод shuffle — для обмена на основе случайных чисел, сгенерированных случайным источником.
Вывод следующий:
до перераспределения: 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;импорт java.util.Iterator;импорт java.util.LinkedHashSet;импорт java.util.Random;импорт java.util.Set;публичный класс Redistribute {public static void main(String[] args) {int[ ] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2};распространение(я);}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("перераспределить индекс");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++;}// выводим результат;System.out.println("after redistribute:");for(int i = 0 ; i<s.length; i++){System.out.print(out[i]+" ");}}}Этот метод сначала генерирует индекс, а затем осуществляет обмен данными на основе нового индекса. Код весь написан в основном методе, что не очень хорошо.
Сгенерированные результаты следующие:
перед перераспределением: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. Этот класс случайных чисел требует отдельного изучения.