描述

题目描述

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

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

示例

输入：
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值：9
说明：
去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9 

知识点：堆, 分治，排序，二分

难度：⭐⭐⭐

题解

图解：

方法一：快排

解题思路：

通过快排思想，将数组通过基准数分为两组，借助二分，判断基准数是否刚好是第k大的元素

算法流程：

• 逆序快排
• 以某个元素作为基准数，维护两个左右指针
• 寻找数组右边开始第一个大于base的元素位置，以及寻找数组左边开始第一个小于base的元素位置
• 最后base再回归到lo，此时保证lo的左边都大于base，右边都小于base（逆序）
• 寻找第k大的元素，不能直接return a[k-1]; 因为可能存在相同的元素

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quickFind(a, 0, n - 1, K);
    }

    // 逆序快排
    private int quickFind(int[] a, int left, int right, int K) {
    	// base 可以取数组长度的随机值进行优化
        int lo = left, hi = right, base = a[left];
        while(lo < hi) {
            // 寻找数组右边开始第一个大于base的元素
            while(lo < hi && a[hi] <= base) {
                hi--;
            }
            // a[lo]一开始由base保存了
            a[lo] = a[hi];
            // 寻找数组左边开始第一个小于base的元素
            while(lo < hi && a[lo] >= base) {
                lo++;
            }
            a[hi] = a[lo];
        }
        // 最后base再回归到lo，此时保证lo的左边都大于base，右边都小于base（逆序）
        a[lo] = base;
        // 寻找第k大的元素，不能直接return a[k-1]; 因为可能存在相同的元素
        if(lo == K - 1) {
            return a[lo];
        } else if(lo > K - 1) {
            return quickFind(a, left, lo - 1, K);
        } else {
            return quickFind(a, lo + 1, right, K);
        }
    }
}

复杂度分析：

时间复杂度：$O(N)O(N)$，平均时间复杂度为O(N)，最坏情况下为O(n^2)，N为数组长度

空间复杂度：$O(N)O(N)$，递归需要用到的栈空间

方法二：堆排序

解题思路：

主要是通过 PriorityQueue 优先级队列来构建最小堆，从而堆顶元素往下，元素大小从大到小

算法流程：

• 优先级队列PriorityQueue构建最小堆，默认升序
• 先保证堆里至少由k个元素，直接加入元素
• 每次堆顶元素小于新加入的元素，则取代该堆顶元素，保证最小堆的结构
• 最后堆顶元素就是第k大元素

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int findKth(int[] nums, int n, int k) {
        // 最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i = 0; i < nums.length; i++) {
            // 先保证堆里至少由k个元素
            if(i < k) {
                minHeap.offer(nums[i]);
                continue;
            }
            int top = minHeap.peek();
            // 每次堆顶元素小于新加入的元素，则取代该堆顶元素，保证最小堆的结构
            if(nums[i] > top) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }
}

复杂度分析：

时间复杂度：$O(nlog(k))O(nlog(k))$，堆排序用到的时间复杂度

空间复杂度：$O(N)O(N)$，构建最小堆用到长度为n的优先级队列