【Java编程题】寻找第K大

一时失言乱红尘 2023-07-11 15:26 13阅读 0赞

# 牛课题：寻找第K大 #

题目说明：

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

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

题目链接：[https://www.nowcoder.com/questionTerminal/e016ad9b7f0b45048c58a9f27ba618bf][https_www.nowcoder.com_questionTerminal_e016ad9b7f0b45048c58a9f27ba618bf]

## 方法1:根据题意利用简单的编程思想 ##

先对数组进行排序-->利用循环从后往前查找记录-->如果遇到的这个数和它的下一个数不相等，则记录数result++，否则对result不进行操作-->直到result和要求的数一样大，退出循环-->此时返回数组的第i个（i定义Wie全局变量）

代码：

import java.util.*;
    public class Main {
        public static int findKth(int [] a,int n,int K){
            Arrays.sort(a);
            int result=0;
            int i;
            for(i=n-1;i>0;i--){
                if(a[i]==a[i-1]){
                    continue;
                }
                else{
                    result+=1;
                    if(result==K){
                        break;
                    }
                }
            }
            return a[i];
        }
    }

## 方法2：利用快排思想 ##

1.进行一次快排，把比基准值小的放在基准值的后面，大的放在基准值的前面，假设得到的基准值是part

2.判断part-low+1=K,如果成立，直接输出a\[p\](因为前半段有K-1个大于a\[p\]的元素，故a\[p\]为第K大的元素)

3.如果part-low+1>K，则第K大的元素在前半段，此时更新high=part-1;继续进行步骤1

4.如果part-low+1<K,则第K大的元素在后半段，此时更新low=part+1,并且K=K-（part-low+1）;继续步骤1

由于常规快排要得到整体有序的数组，因此此方法可以去掉“一半”的元素，故实际的复杂度不是O(nlogn)，而是O(n);

代码如下：

import java.util.*;
    
    public class Main {
          public static  int findK(int [] a,int n,int K){
            return find(a,0,n-1,K);
        }
    
        private static  int find(int[] a, int low, int high, int K) {
            int part=partatin(a,low,high);
            if(K==part-low+1){
                return a[part];
            }
            else if(K>part-low+1){
                return find(a,part+1,high,K-part+low-1);
            }
            else{
                return find(a,low,part-1,K);
            }
        }
    
        private static int partatin(int[] a, int low, int high) {
            int key=a[low];
            while(low<high){
                while(low<high&&a[high]<=key){
                    high--;
                }
                a[low]=a[high];
                while(low<high&&a[low]>=key){
                    low++;
                }
                a[high]=a[low];
            }
            a[low]=key;
            return low;
        }
    }

[https_www.nowcoder.com_questionTerminal_e016ad9b7f0b45048c58a9f27ba618bf]: https://www.nowcoder.com/questionTerminal/e016ad9b7f0b45048c58a9f27ba618bf