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)

实现代码如下：

 package algorithms;

 import java.util.Arrays;

 import java.util.Random;

 public class SelectionProblem {

     //static StringBuilder logger = new StringBuilder(); // debug

     //static String NEWLINE = "\n"; // debug

     /**

      * @param a the array

      * @param low the lower bound (inclusive)

      * @param high the upper bound (exclusive)

      * @param i indicate that the i-th order statistic is our target, i starts from 1

      * @return the i-th order statistic

      * */

     public static <T extends Comparable<T>>

     T randomizedSelect(T[] a, int low, int high, int i) {

         --high; // high the upper bound (exclusive)

         return _randomizedSelect(a, low, high, i);

     }

     private static <T extends Comparable<T>>

     T _randomizedSelect(T[] a, int low, int high, int i) {

         if (low == high) {

             return a[low]; // target found

         }

         // else, partition

         int pivot = randomizedPartition(a, low, high);

         int k = pivot - low + 1;

         if (k == i) { // if pivot is our target

             return a[pivot];

         } else if (k > i) { // if pivot is too large

             return _randomizedSelect(a, low, pivot-1, i);

         } else { // if pivot is too small

             return _randomizedSelect(a, pivot+1, high, i-k);

         }

     }

     private static <T extends Comparable<T>>

     int randomizedPartition(T[] a, int low, int high) {

         int pivotIndex = randomIndex(low, high+1);

         // logger.append("pivotIndex:"+pivotIndex+NEWLINE); // debug

         return Partition.doPartition(a, low, high+1, pivotIndex);

     }

     private static final Random random = new Random();

     // low (inclusive), high (exclusive)

     private static int randomIndex(int low, int high) {

         if (high==low) {

             return low;

         }

         return random.nextInt(high-low) + low;

     }

     // test

     public static void main(String[] args) {

         Integer[] a = new Integer[]{29, 36, 44, 12, 29, 24, 28, 74, 54, 56};

         System.out.println(Arrays.toString(a));

         Integer result = SelectionProblem.randomizedSelect(a, 0, a.length, 10);

         //if (result != 36) { // debug

         //    System.out.println(logger); // debug

         //} // debug

         System.out.println("result:"+result);

         //System.out.println(Arrays.toString(a)); // debug

         QuickSort.sort(a, 0, a.length);

         System.out.println(Arrays.toString(a));

     }

 }

巴特西

Selection Problem （选择问题）

最新文章

热门文章