Kth Largest Element in an Array

Tags: Heap, Divide and Conquer, Medium

Question

Problem Statement

Find the kth largest element in an unsorted array. Note that it is the kth
largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Credits:

Special thanks to @mithmatt for
adding this problem and creating all test cases.

题解

找第 K 大数，基于比较的排序的方法时间复杂度为 O(n), 数组元素无区间限定，故无法使用线性排序。由于只是需要找第 K 大数，这种类型的题通常需要使用快排的思想解决。Quick Sort 总结了一些经典模板。这里比较基准值最后的位置的索引值和 K 的大小关系即可递归求解。

Java

  1. public class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         if (nums == null || nums.length == 0) {
  4.             return Integer.MIN_VALUE;
  5.         }
  7.         int kthLargest = qSort(nums, 0, nums.length - 1, k);
  8.         return kthLargest;
  9.     }
  11.     private int qSort(int[] nums, int left, int right, int k) {
  12.         if (left >= right) {
  13.             return nums[right];
  14.         }
  16.         int m = left;
  17.         for (int i = left + 1; i <= right; i++) {
  18.             if (nums[i] > nums[left]) {
  19.                 m++;
  20.                 swap(nums, m, i);
  21.             }
  22.         }
  23.         swap(nums, m, left);
  25.         if (k == m + 1) {
  26.             return nums[m];
  27.         } else if (k > m + 1) {
  28.             return qSort(nums, m + 1, right, k);
  29.         } else {
  30.             return qSort(nums, left, m - 1, k);
  31.         }
  32.     }
  34.     private void swap(int[] nums, int i, int j) {
  35.         int tmp = nums[i];
  36.         nums[i] = nums[j];
  37.         nums[j] = tmp;
  38.     }
  39. }

源码分析

递归的终止条件有两个，一个是左边界的值等于右边界(实际中其实不会有 l > u), 另一个则是索引值 m + 1 == k.
这里找的是第 K 大数，故为降序排列，for 循环中使用nums[i] > nums[left] 而不是小于号。

复杂度分析

最坏情况下需要遍历 n + n - 1 + … + 1 = O(n^2), 平均情况下 n + n/2 + n/4 + … + 1 = O(2n)=O(n). 故平均情况时间复杂度为 O(n). 交换数组的值时使用了额外空间，空间复杂度 O(1).