首页 > 代码库 > Selection Problem （选择问题）
Selection Problem （选择问题）
在一个由n个元素组成的集合中，第i个“顺序统计量（order statistic）”是该集合中第i小的元素。例如，在一个由n个元素组成的集合中，最小值是第1个顺序统计量，最大值是第n个顺序统计量。而“中位数（median）”总是出现在low((n+1)/2)或者high((n+1)/2)处，其中low是向下取整（“下中位数”），high是向上取整（“上中位数”），当n为奇数的时候，只有“下中位数”，而n为偶数的时候，同时有“下中位数”和“上中位数”。
选择问题的定义如下。
输入：一个包含n个不同的数的集合A和一个数i，i属于范围[1,n]
输出：集合A中的一个元素x，x恰好大于A中的其他i-1个元素
通过排序的方法可以解决这个问题，比如堆排序、归并排序。时间可以达到O(n*lg(n))
下面讨论一个实用的算法，平均情况下运行时间为O(n)
此程序利用了快速排序的partition子程序（随机选择pivot的版本），因为partition总是把比pivot小的划分到左边，比pivot大的划分到右边，所以利用这一点（但是randomizedSelect不会向快速排序一样递归地处理划分出来的两边，而是只处理左边或者右边，因此要更快一些）完成选择。
此算法平均性能比较好，因为是随机化的划分，不会有哪一组特定的输入导致其最坏情况的发生。
平均时间是O(n)，最坏时间是O(n^2)
实现代码如下：
1 package algorithms; 2 3 import java.util.Arrays; 4 import java.util.Random; 5 public class SelectionProblem { 6 7 //static StringBuilder logger = new StringBuilder(); // debug 8 //static String NEWLINE = "\n"; // debug 9 10 /**11 * @param a the array12 * @param low the lower bound (inclusive)13 * @param high the upper bound (exclusive)14 * @param i indicate that the i-th order statistic is our target, i starts from 115 * @return the i-th order statistic16 * */17 public static <T extends Comparable<T>>18 T randomizedSelect(T[] a, int low, int high, int i) {19 --high; // high the upper bound (exclusive)20 return _randomizedSelect(a, low, high, i);21 }22 23 private static <T extends Comparable<T>>24 T _randomizedSelect(T[] a, int low, int high, int i) {25 if (low == high) {26 return a[low]; // target found27 }28 // else, partition29 int pivot = randomizedPartition(a, low, high);30 int k = pivot - low + 1;31 if (k == i) { // if pivot is our target32 return a[pivot];33 } else if (k > i) { // if pivot is too large34 return _randomizedSelect(a, low, pivot-1, i);35 } else { // if pivot is too small36 return _randomizedSelect(a, pivot+1, high, i-k);37 }38 }39 40 private static <T extends Comparable<T>>41 int randomizedPartition(T[] a, int low, int high) {42 int pivotIndex = randomIndex(low, high+1);43 // logger.append("pivotIndex:"+pivotIndex+NEWLINE); // debug44 return Partition.doPartition(a, low, high+1, pivotIndex);45 }46 47 private static final Random random = new Random();48 // low (inclusive), high (exclusive)49 private static int randomIndex(int low, int high) {50 if (high==low) {51 return low;52 }53 return random.nextInt(high-low) + low;54 }55 56 // test57 public static void main(String[] args) {58 Integer[] a = new Integer[]{29, 36, 44, 12, 29, 24, 28, 74, 54, 56};59 System.out.println(Arrays.toString(a));60 Integer result = SelectionProblem.randomizedSelect(a, 0, a.length, 10);61 //if (result != 36) { // debug62 // System.out.println(logger); // debug63 //} // debug64 System.out.println("result:"+result);65 //System.out.println(Arrays.toString(a)); // debug66 QuickSort.sort(a, 0, a.length);67 System.out.println(Arrays.toString(a));68 }69 70 }
Selection Problem （选择问题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。