Algorithm 05 : 给定一个数组，寻找第K大的数

给定一个无序数组，求数组中第K大的数。

答：求一个数组中第K大数可以借用快速排序算法的思想，主要思路如下：
      （1）在数组中随机选择一个数作为支点。
      （2）将比作为支点数大的所有数放在这个支点的左边，支点放在数组中间的位置。
      （3）设支点左边元素的个数为L，那么可以分以下三种情况：
              （a）当K=L的时候，直接返回支点即是所要求的第K大的数。
              （b）当K<L的时候，在支点左边的数中继续寻找第K大的数。
              （c）当K>L的时候，在支点右边的数中继续寻找第(K-L)大的数。

         基于上述想法的代码实现如下：

/** @author YuHuang
   * @version 2011-10-11
   * This program is only for algorithm training.
   *
   */

import java.lang.*;
import java.lang.RuntimeException;
import java.util.Random;

public class FindKthNumber {
        private int[] dataArray;
        private Random random = new Random();

        private FindKthNumber() {}

        public FindKthNumber(int[] dataArray){
                if(dataArray!=null && dataArray.length!=0){
                        this.dataArray = dataArray;
                }else{
                        throw new RuntimeException("Array should not be null!");
                }
        }

        public int doFind(int left,int right,int k){
                int pivot;
                int m=left;
                int count=1;

                System.out.println("k="+k);
                if(k<=0||k>right-left+1){
                        return -1;
                }

                pivot=left+(java.lang.Math.abs(random.nextInt()))%(right-left+1);
                swap(left,pivot);

                for(int index = left+1;index<=right;++index){
                        if(this.dataArray[index]>this.dataArray[left]){
                                swap(++m,index);
                                ++count;
                        }
                }

                swap(left,m);

                if(k<count){
                        return doFind(left,m-1,k);
                }else if(k>count){
                        return doFind(m+1,right,k-count);
                }else{
                        return m;
                }

        }

        private void swap(int fIndex,int lIndex){
                int temp = this.dataArray[fIndex];
                this.dataArray[fIndex]=this.dataArray[lIndex];
                this.dataArray[lIndex]=temp;
        }

        public static void main(String[] args){
                int[] dataArray=new int[]{1,6,3,8,9,18,22,45,11,99};

                try{
                        FindKthNumber fkn = new FindKthNumber(dataArray);
                        int k=4;
                        int result=fkn.doFind(0,dataArray.length-1,k);
                        result = result==-1? result:dataArray[result];
                        System.out.println("The "+k+"th number in dataArray is "+result);
                }catch(Exception e){
                        e.printStackTrace();
                }
        }
}

运行的结果如下：
Lab-Computer-0db2f6:JavaExercises labuser$ java FindKthNumber
k=4
k=4
k=3
The 4th number in dataArray is 18

知识扩展：容易想到对上面的算法进行小小的改造就可以求出一个给定数组中的前K大的所有数字。即在输出的时候，如果result的值不为－1，则输出数组中0~result之间的所有数就是所要求解的前K大数的集合。

评论

1 楼 yjc2020 2014-03-05  

求第几大的数后还要给出其在原数组中的位置，你这个是不是还要再遍历一次