选出数组中从i到j的第k小的元素(不用对数组排序)
package com.flyingh.demo;import java.util.Random;public class Demo {public static void main(String[] args) {int[] arr = { 3, 6, 5, 8, 7, 2, 1, 9, 0, 4 };System.out.println(select(arr, 1, 8, 5));}public static int select(int[] arr, int i, int j, int k) {if (k < 1 || k > j - i + 1) {return -1;}// int t = randomizedPartition(arr, i, j);int t = randomizedPartition2(arr, i, j);if (t == i + k - 1) {return arr;} else if (t < i + k - 1) {return select(arr, t + 1, j, k + i - 1 - t);} else {return select(arr, i, t, k);}}private static int randomizedPartition2(int[] arr, int m, int n) {int t = new Random().nextInt(n + 1 - m) + m;int tmp = arr;arr = arr;arr = tmp;int i = m - 1;for (int j = m; j < n; ++j) {if (arr < arr) {int temp = arr[++i];arr = arr;arr = temp;}}int temp = arr;arr = arr;arr = temp;return i + 1;}@SuppressWarnings("unused")private static int randomizedPartition(int[] arr, int m, int n) {int t = new Random().nextInt(n + 1 - m) + m;int tmp = arr;arr = arr;arr = tmp;int key = arr;while (m < n) {while (m < n && arr >= key) {--n;}arr = arr;while (m < n && arr <= key) {++m;}arr = arr;}arr = key;return m;}}
页:
[1]