首页 > 试题广场 >

整数无序数组求第K大数

[编程题]整数无序数组求第K大数
  • 热度指数：17 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定无序整数序列，求其中第K大的数，例如{45，67，33，21}，第2大数为45

输入描述:
输入第一行为整数序列，数字用空格分隔，如：45 67 33 21
输入第二行一个整数K，K在数组长度范围内，如：2


输出描述:
输出第K大的数，本例为第2大数：45
示例1

输入

45 67 33 21
2

输出

45
算法知识视频讲解
添加回答
pein531头像 pein531
可以用快速选择算法，均摊时间复杂度为O(N)。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int n = strArr.length;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        int k = Integer.parseInt(br.readLine());
        System.out.println(quickSelect(arr, 0, n - 1, n - k));
    }
    
    private static int quickSelect(int[] arr, int begin, int end, int k) {
        if(begin == end) return arr[begin];
        int pivot = arr[begin + (int)Math.ceil(Math.random()*(end - begin))];
        int[] pivotRange = partition(arr, begin, end, pivot);
        if(k < pivotRange[0]){
            return quickSelect(arr, begin, pivotRange[0] - 1, k);
        }else if(k > pivotRange[1]){
            return quickSelect(arr, pivotRange[1] + 1, end, k);
        }else{
            return arr[k];
        }
    }
    
    private static int[] partition(int[] arr, int begin, int end, int pivot) {
        int less = begin - 1, more = end + 1;
        int cur = begin;
        while(cur < more){
            if(arr[cur] < pivot){
                swap(arr, ++less, cur++);
            }else if(arr[cur] > pivot){
                swap(arr, --more, cur);
            }else{
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
但这种做法太不新鲜了，这里再改个BFPRT算法的版本，能够严格达到O(N)的时间复杂度。两个算法的主流程完全相同，只有选择划分点进行partition的时候有所不同，BFPRT算法选择这个划分点的时候有所讲究，能够控制左右两边的数据规模。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int n = strArr.length;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        int k = Integer.parseInt(br.readLine());
        System.out.println(bfprt(arr, 0, n - 1, n - k));
    }
    
    private static int bfprt(int[] arr, int begin, int end, int k) {
        if(begin == end) return arr[begin];
        int pivot = medianOfMedians(arr, begin, end);
        int[] pivotRange = partition(arr, begin, end, pivot);
        if(k < pivotRange[0]){
            return bfprt(arr, begin, pivotRange[0] - 1, k);
        }else if(k > pivotRange[1]){
            return bfprt(arr, pivotRange[1] + 1, end, k);
        }else{
            return arr[k];
        }
    }
    
    private static int[] partition(int[] arr, int begin, int end, int pivot) {
        int less = begin - 1, more = end + 1;
        int cur = begin;
        while(cur < more){
            if(arr[cur] < pivot){
                swap(arr, ++less, cur++);
            }else if(arr[cur] > pivot){
                swap(arr, --more, cur);
            }else{
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }
    
    private static int medianOfMedians(int[] arr, int begin, int end) {
        int len = end - begin + 1;
        int[] mArr = new int[len / 5 + (len % 5 == 0? 0: 1)];
        for(int i = 0; i < mArr.length; i++){
            int beginI = begin + i*5;
            int endI = beginI + 4;
            mArr[i] = getMedian(arr, beginI, Math.min(endI, end));
        }
        return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);
    }
    
    private static int getMedian(int[] arr, int begin, int end) {
        insertSort(arr, begin, end);
        int sum = begin + end;
        int mid = sum / 2 + sum % 2;
        return arr[mid];
    }
    
    // 不超过5个数用插入排序，常数项极低
    private static void insertSort(int[] arr, int begin, int end) {
        for(int i = begin + 1; i <= end; i++){
            for(int j = i; j > begin; j--){
                if(arr[j - 1] > arr[j]){
                    swap(arr, j - 1, j);
                }else{
                    break;
                }
            }
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
遗憾的是，虽然理论上BFPRT算法是更优秀的O(N)算法，但是这道题的测试用例下，貌似还是快速选择算法运行得更快一些。
编辑于 2021-12-06 10:03:41 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 PHP工程师 招商银行信用卡中心 Java工程师
上传者：小小
难度：
1条回答 955浏览

热门推荐

通过挑战的用户

相关试题

整数无序数组求第K大数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号