算法：数组中第k大的数

题目描述

数组中第k大的数是一道十分经典的题目，题目表述可以如下

You are given a set S of n integers in an array and also an integer k ∈ [1, n]. Design an algorithm to find the k-th largest integer of S.

给定 一个数组，返回数组中第k大的元素

215. 数组中的第K个最大元素 - 力扣（LeetCode） (leetcode-cn.com)

剑指 Offer II 076. 数组中的第 k 大的数字 - 力扣（LeetCode） (leetcode-cn.com)

题解

分治算法（快速排序）

首先，一个非常简单的思路，我们直接先将整个数组进行排序，然后就可以直接找到第k大的数字了，这样的时间复杂度是O(nlogn)。但是实际上，我们并不需要将整个数组进行排序，我们在排序的过程中已经可以找到第k大的元素。下面这个算法就是基于快速排序算法找出了第k大的数字(参考《算法导论》以及课上的课件)。

算法思路：首先在数组中随机选取一个下标当做pivot，然后进行partition，将比pivot的值大的放在左侧，比pivot的值小的放在右侧，接下来分三种情况：

1. pivot==k-1, 我们就已经找到了第k大的元素
2. pivot<k-1, 我们需要在pivot之后的数字中找到第k-pivot-1大的元素
3. pivot>k-1, 我们需要在pivot之前的数字中找到第k大的元素

（注：这里是k-1是因为pivot是下标从0开始，k从1开始）

我们还可以对这个算法进行一定的优化，如果说我们随机选取的pivot的位置非常靠左或者靠右，那么这个时候我们在递归之前可能只能排除掉非常少的部分元素，我们可以希望pivot落在数组范围的中间1/3部分，如果不在的话，我们重新选择一个pivot (实际上感觉这样子提升的效果也不是很好？)下面是代码部分

import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class KSelection {

    Random random = new Random();

    public Comparable kSelectionSort(Comparable[] arr, int k) {
        if (k > arr.length || k <= 0) return -1;
        return quickKSelection(arr, 0, arr.length - 1, k - 1);
    }

    private Comparable quickKSelection(Comparable[] arr, int lo, int hi, int k) {
        if (lo == hi) return arr[hi];
        int pivot = partition(arr, lo, hi);
        if (pivot > k) return quickKSelection(arr, lo, pivot - 1, k);
        else if (pivot < k) return quickKSelection(arr, pivot + 1, hi, k);
        else return arr[pivot];
    }

    private int partition(Comparable[] arr, int lo, int hi) {
        int pivot= random.nextInt(hi-lo+1)+lo;
        swap(arr, pivot, lo);
        pivot = lo;
        int i = lo, j = hi + 1;
        while (true) {
            while (arr[++i].compareTo(arr[pivot]) > 0) if (i == hi) break;
            while (arr[pivot].compareTo(arr[--j]) > 0 ) if (j == lo) break;
            if (i >= j) break;
            swap(arr, i, j);
        }
        swap(arr, pivot, j);
        pivot = j;
        if (pivot >= lo + (hi - lo) / 3 && pivot <= hi - (hi - lo) / 3)
            return pivot;
        else return partition(arr, lo, hi);
    }

    private void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

时间复杂度：\(f(n)\le O(n)+f(\lceil2n/3\rceil)\),根据Master's theorem, 时间复杂度为O(n)。空间复杂度：函数递归占用栈空间O(logn)。

最大堆

另一个思路也非常容易，就是维护一个大根堆，然后依次将每个元素压入队列中，然后最后将最上面k-1个元素依次弹出，现在堆顶的元素就是数组中第k大的元素。时间复杂度O(nlogn)。代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : nums) queue.add(num);
        for (int i = 0; i < k - 1; i++) queue.poll();
        return queue.poll();
    }
}