В этой статье описывается линейная операция выбора времени, реализованную Java на основе алгоритма разделения и завоевания. Поделитесь этим для вашей ссылки, следующим образом:
Проблема выбора линейного времени: Учитывая n элементов и целое число k, 1≤k≤n, необходимо выяснить наименьший элемент этих n -элементов (заданный линейный набор здесь неупорядочен).
Случайно разделенный линейный выбор
Линейный метод выбора времени, метод случайного деления может имитировать конструкцию рандомизированного алгоритма быстрого сортировки. Основная идея состоит в том, чтобы рекурсивно разделить входной массив. В отличие от быстрой сортировки, она только рекурсивно обрабатывает один из разделенных субррей.
Объяснение программы: используйте случайную функцию для генерации эталона разделения, разделите массив A [P: R] на два субрайя A [P: i] и A [I+1: R], чтобы каждый элемент в [P: i] не больше каждого элемента в [i+1: r]. Затем «j = i-p+1» вычисляет количество элементов j в [P: i]. Если k <= j, то самый маленький элемент k-th в [P: r] находится в субмарке a [p: i], и если k> j, самый маленький элемент K-й в подполах a [i+1: r]. ПРИМЕЧАНИЕ. Поскольку известно, что элементы в суб-араме A [P: i] все меньше, чем можно найти маленький элемент K-th, маленький элемент K-th в [P: R], который можно найти, является маленьким элементом K-th в [I+1: R].
Например, в худшем случае: когда всегда найден самый маленький элемент, он всегда разделен на самый большой элемент, который является сложностью времени O (n^2) . Тем не менее, средняя сложности времени линейно связана с N, который является O (n)
пакет Math; import java.util.scanner; import java.util.random; public class randomselect {public static void swap (int x, int y) {int temp = x; x = y; y = темп; } public int random (int x, int y) {случайный случайный = new random (); int num = random.nextint (y)%(y - x + 1) + x; вернуть num; } public int partition (int [] list, int low, int high) {int tmp = list [low]; // Первая из массива-центральная ось, в то время как (low <High) {while (low <high && list [high]> tmp) {high--; } list [low] = list [high]; // записывает меньше, чем центральная ось перемещается в нижний конец, в то время как (low <High && list [low] <tmp) {low ++; } list [high] = list [low]; // записывает больше, чем центральная ось перемещается в список высокого уровня} [low] = tmp; // записывают больше, чем центральная ось, возвращаются низко; // Возвращение в положение центральной оси} public int randomizedPartition (int [] массивы, int left, int справа) {int i = Random (слева, справа); своп (массивы [i], массивы [слева]); вернуть раздел (массивы, слева, справа); } public int randomizedSelect (int [] массивы, int left, int right, int k) {if (left == right) {return arrays [left]; } int i = Рандомизированная частица (массивы, слева, справа); int j = i - слева + 1; if (k <= j) {return randomizedselect (массивы, слева, i, k); } else {return randomizedSelect (массивы, i+1, справа, KJ); }} public static void main (string args []) {System.out.println ("wulin.com Результат теста:"); int [] a = {7,5,3,4,8,6,9,1,2}; for (int i = 0; i <9; i ++) {System.out.print (a [i]+""); } System.out.println (); RandomSelect r = new RandomSelect (); System.out.println («Какой самый маленький элемент вы хотите запросить в массиве?»); @Suppresswarnings ("resource") сканер sc = new Scanner (System.in); int m = sc.nextint (); int n = r.randomizedselect (a, 0,8, m); System.out.println («Th» в этом массиве » + M +» самый маленький элемент: « + n); }}Результаты работы:
Для получения дополнительной информации об алгоритмах Java, читатели, которые заинтересованы в этом сайте, могут просмотреть темы: «Учебное пособие по структуре данных Java и алгоритм», «Сводка операции Java Dom Node», «Сводка Java File и каталог
Я надеюсь, что эта статья будет полезна для всех Java Programming.