Kth Largest Element in an Array

描述

Find the k-th largest element in an unsorted array.

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.

分析

这题是一道很好的面试题目，

  • 题目短小，很快就能说清题意
  • 有很多种解法。从简单到复杂的解法都有，梯度均匀。

  • 不需要预先知道特殊领域知识。
    这题有很多思路：

  • 按从大到小全排序，然后取第k个元素，时间复杂度O(nlogn)，空间复杂度O(1)

  • 利用堆进行部分排序。维护一个大根堆，将数组元素全部压入堆，然后弹出k次，第k个就是答案。时间复杂度O(klogn)，空间复杂度O(n)
  • 选择排序，第k次选择后即可得到第k大的数，时间复杂度O(nk)，空间复杂度O(1)
  • 堆排序，维护一个k大小的小根堆，将数组中的每个元素与堆顶元素进行比较，如果比堆顶元素大，则删除堆顶元素并添加该元素，如果比堆顶元素小，则什么也不做，继续下一个元素。时间复杂度O(nlogk)，空间复杂度O(k)。

  • 利用快速排序中的partition思想，从数组中随机选择一个元素x，把数组划分为前后两部分sa和sb，sa中的元素小于x，sb中的元素大于或等于x。这时有两种情况：

    • sa的元素个数小于k，则递归求解sb中的第k-|sa|大的元素
    • sa的元素个数大于或等于k，则递归求解sa中的第k大的元素

时间复杂度O(n)，空间复杂度O(1)

思路4和5比较高效，可以接受，其他思路太慢了，不采纳。

思路4 partition

  1. // Kth Largest Element in an Array
  2. // Time complexity: O(nlogk), Space complexity: O(k)
  3. public class Solution {
  4.     public int findKthLargest(int[] nums, int k) {
  5.         final Queue<Integer> q = new PriorityQueue<>();
  7.         for (int x : nums) {
  8.             if (q.size() < k) {
  9.                 q.offer(x);
  10.             } else {
  11.                 final int top = q.peek();
  12.                 if (x > top) {
  13.                     q.poll();
  14.                     q.offer(x);
  15.                 }
  16.             }
  17.         }
  18.         return q.peek();
  19.     }
  20. }

思路5 小根堆

  1. // Kth Largest Element in an Array
  2. // Time complexity: O(n), Space complexity: O(1)
  3. public class Solution {
  4.     public int findKthLargest(int[] nums, int k) {
  5.         quickSort(nums, 0, nums.length - 1);
  6.         return nums[nums.length - k];
  7.     }
  8.     private static int findKthLargest(int[] nums, int begin, int end, int k) {
  9.         if (begin + 1 == end && k == 1) return nums[0];
  11.         final int pos = partition(nums, begin, end - 1);
  12.         final int len = pos - begin;
  14.         if (len == k) {
  15.             return nums[pos-1];
  16.         } else if (len < k) {
  17.             return findKthLargest(nums, pos, end, k - len);
  18.         } else {
  19.             return findKthLargest(nums, begin, pos, k);
  20.         }
  21.     }
  22.     private static void quickSort(int[] nums, int left, int right) {
  23.         if (left < right) {
  24.             final int pos = partition(nums, left, right);
  25.             quickSort(nums, left, pos - 1);
  26.             quickSort(nums, pos + 1, right);
  27.         }
  28.     }
  29.     private static int partition(int[] nums, int i, int j) {
  30.         final int pivot = nums[i];
  31.         while (i < j) {
  32.             while (i < j && nums[j] >= pivot) --j;
  33.             nums[i] = nums[j];
  34.             while(i < j && nums[i] <= pivot) ++i;
  35.             nums[j] = nums[i];
  36.         }
  37.         nums[i] = pivot;
  38.         return i;
  39.     }
  40. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/sorting/quick-sort/kth-largest-element-in-an-array.html