牛客Top200---寻找第K大的数（java）_第 k 大的整数** 分数 20 作者 李祥 单位 湖北经济学院 求 n 个整数中第 k(1≤k≤

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

题目解法

最简单的方法，但没有按题目要求，直接调用java的数组排序接口

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        Arrays.sort(a);
        return a[n-K];//排序后，倒数第K个，即第K大的数
    }
}
1
2
3
4
5
6
7
8
9

快速排序解法

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        quickSort(a,0,a.length-1);
        return a[n-K];
    }
    //快速排序
    public static void quickSort(int[] arr,int low ,int high){
        if (low > high){
            return;
        }
        int i = low;
        int j = high;
        int base = arr[low];//基准
        int temp;//辅助变量
        while(i < j){
            //首先看右边，往左边递减
            while (i < j && base <= arr[j]){
                j--;
            }
            while (i < j && base >= arr[i]){
                i++;
            }
            //上面两个循环执行后，就会index为i位置比base大，需要换到右边，index为j比base小，需要换到左边
            if (i < j){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //循环跳出i=j，基准再和相等处交换
        arr[low] = arr[i];
        arr[i] = base;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

此题就是考察快速排序，其他常用排序也可回顾下，见 常用排序介绍