欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

每日一题02

程序员文章站 2022-03-15 21:13:55
...

题目描述:

有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。

在看到这道题的第一反应就是如下代码,虽然牛客上提交过去了,但是这是投机取巧的方法,主要是忘记了快速排序的思想。

​​public class Finder {
        public int findKth(int[] a, int n, int K) {
            // write code here
            Arrays.sort(a);
            for(int i=1;i<K;i++){
                if(a[i]==a[i-1]){
                    K++;
                }
            }
            return a[a.length-K];
        }
    }
   ​​

在复习了快速排序的方法之后,这道题应该是用快排的思想:例如找49个元素里面第24大的元素,那么按如下步骤:1.进行一次快排(将大的元素放在前半段,小的元素放在后半段),假设得到的中轴为p,2.判断p-low+1==k,如果成立,直接输出a[p],(因为前半段有k-1个大于a[p]的元素,故a[p]为第K大的元素)3.如果p-low+1>k,则第K大的元素在前半段,此时更新high=p-1,继续进行步骤1,4.如果p-low+1<k,则第K大的元素在后半段,此时更新low=p+1,且k=k-(p-low+1),继续进行步骤1,由于常规快排要得到整体有序的数组,而此方法每次可以去掉“一半”的元素,故实际的复杂度不是O(nlgn),而是O(n).

​public int FindK(int[] a,int n,int K){
       return findK(a,0,n-1,K);
   }
    private int findK(int[] a, int low, int high, int K) {
       int part=partition(a,low,high);
       if(part-low+1==K){
           return a[part];
       }
       if(K>part-low+1){
           return findK(a,part+1,high,K-part+low-1);
       }
       else{
           return findK(a,low,part-1,K);
       }
    }
    private int partition(int[] a, int low, int high) {
       int pivot=a[low];
       int i=low;
       int j=high;
       while(i<j){
           while(i<j&&a[j]<=pivot){
               j--;
           }
           a[i]=a[j];
           while(i<j&&a[i]>=pivot){
               i++;
           }
           a[j]=a[i];
       }
       a[i]=pivot;
       return i;
    }​