题目介绍

力扣215题：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

分析

要寻找数组中第K大的元素，首先能想到的，当然就是直接排序。只要数组是有序的，那么接下来取出倒数第K个元素就可以了。

public class KthLargestElement {
    // 直接调语言内置的排序方法
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

我们知道，java的Arrays.sort()方法底层就是快速排序，所以时间复杂度为O(nlogn)。如果实际遇到这个问题，直接调类库方法去排序，显然是不能让面试官满意的。我们应该手动写出排序的算法。

选择、冒泡和插入排序时间复杂度是O(n^2)，性能较差；二计数排序、桶排序和基数排序尽管时间复杂度低，但需要占用大量的额外空间，而且只有在数据取值范围比较集中、桶数较少时效率比较高。所以实际应用中，排序的实现算法一般采用快速排序，或者归并和堆排序。

对于这道题目而言，其实还可以进一步优化：因为我们只关心第K大的元素，其它位置的元素其实可以不排。基于这样的想法，显然归并这样的算法就无从优化了；但快排和堆排序可以。

方法一：基于快速排序的选择

我们可以改进快速排序算法来解决这个问题：在分区（partition）的过程当中，我们会对子数组进行划分，如果划分得到的位置 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是“快速选择”算法。另外，我们知道快速排序的性能和“划分”出的子数组的长度密切相关。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。

public int findKthLargest(int[] nums, int k) {
    return quickSelect( nums, 0, nums.length - 1, nums.length - k );
}
// 为了方便递归，定义一个快速选择方法
public int quickSelect( int[] nums, int start, int end, int index ){
    int q = randomPatition( nums, start, end );
    if (q == index){
        return nums[q]; 
    } else {
        return q > index ? quickSelect(nums, start, q - 1, index) : quickSelect(nums, q + 1, end, index);
    }
}
// 定义一个随机分区方法
public int randomPatition( int[] nums, int start, int end ){
    Random random = new Random();
    int randIndex = start + random.nextInt(end - start + 1); 
    swap(nums, start, randIndex);
    return partition(nums, start, end);
}
// 定义一个分区方法
public int partition( int[] nums, int start, int end ){
    int pivot = nums[start];
    int left = start; 
    int right = end; 
    while ( left < right ){
        while ( left < right && nums[right] >= pivot )
            right --;
        nums[left] = nums[right];
        while ( left < right && nums[left] <= pivot )
            left ++;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}
// 定义一个交换元素的方法
public void swap( int[] nums, int i, int j ){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

复杂度分析

• 时间复杂度：O(n)，证明过程可以参考《算法导论》9.2：期望为线性的选择算法。
• 空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为O(logn)。

方法二：基于堆排序的选择

我们也可以使用堆排序来解决这个问题。基本思路是：构建一个大顶堆，做 k−1 次删除操作后堆顶元素就是我们要找的答案。

在很多语言中，都有优先队列或者堆的的容器可以直接使用，但是在面试中，面试官更倾向于让更面试者自己实现一个堆。所以这里我们要手动做一个类似堆排序的实现。
代码演示如下：

public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    int heapSize = n;
    // 构建大顶堆
    buildMaxHeap( nums, heapSize );
    // 删除k-1次堆顶元素
    for ( int i = n - 1; i > n - k; i-- ){
        swap( nums, 0, i );
        heapSize --;
        maxHeapify( nums, 0, heapSize );
    }
    return nums[0];
}

// 构建大顶堆的方法
public void buildMaxHeap( int[] nums, int heapSize ){
    for ( int i = heapSize / 2 - 1; i >= 0; i-- ){
        maxHeapify(nums, i, heapSize);
    }
}
public void maxHeapify( int[] nums, int top, int heapSize ){
    int left = top * 2 + 1;
    int right = top * 2 + 2;
    int largest = top;
    if ( right < heapSize && nums[right] > nums[largest] ){
        largest = right;
    }
    if ( left < heapSize && nums[left] > nums[largest] ){
        largest = left;
    }
    if ( largest != top ){
        swap( nums, top, largest );
        maxHeapify(nums, largest, heapSize);
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，建堆的时间代价是 O(n)，k-1次删除的总代价是 O(klogn)，因为 k<n，故渐进时间复杂为O(n+klogn)=O(nlogn)。
• 空间复杂度：O(logn)，即递归使用栈空间的空间代价。