【堆】B004_数组中的第 K 个最大元素（排序 | PQ | minHeapify | 快排思想）

一、题目描述

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.

Input: [3,2,1,5,6,4] and k = 2
Output: 5

二、题解

方法一：PQ 维护 k 个元素的最小堆

/**
 * @date: 2/20/2020 10:11 AM
 * @Execution info：6ms 击败 63.7% 的j，MB 击败 5% 的j
 */
public int findKthLargest(int[] nums, int k) {

  PriorityQueue<Integer> pQ = new PriorityQueue<>();
  for (int n : nums) {
    pQ.add(n);
    if (pQ.size() > k) {
      pQ.poll();
    }
  }
  return pQ.peek();
}

复杂度分析

• 时间复杂度：$O(N × logk)$O(N×logk)，N 为 nums 的元素个数，k 为最小堆中的元素。
• 空间复杂度：$O(k)$O(k)，

---

方法二：自建 minHeapify

思路与算法

• 默认使用数组的前k个元素创建一个元素个数为 k 的小顶堆。
• 堆顶的元素是最小的，也当前堆中的 k 个元素的第 k 大元素，当然还有后面的逻辑。
• 遍历剩下的数组元素，只有比堆顶的元素要大，我们才让它替换对顶元素，然后重新调整堆结构。

/**
 * @date: 2/20/2020 10:18 AM
 * @Execution info：1ms 击败 99.97% 的j，MB 击败 5% 的j
 */
public int findKthLargest1(int[] nums, int k) {
  //前K个元素原地建小顶堆
  buildHeap(nums, k);
  //遍历剩下的元素，若有元素比堆顶小，则跳过；否则，交换后重新堆化
  for (int i = k; i < nums.length; i++) {
    if (nums[i] > nums[0]) {
      swap(nums, i, 0);
      heapify(nums, k, 0);
    }
  }
  return nums[0];
}

// 从最后一个非叶子结点开始将数组堆化
public void buildHeap(int[] data, int K) {
  for (int i = K/2 - 1; i >= 0; i--)
    heapify(data, K, i);
}

private void heapify(int[] data, int K, int parentIndex) {

  int minIndex = parentIndex;

  while (true) {
    int l = parentIndex * 2 + 1;
    int r = parentIndex * 2 + 2;

    if (l < K && data[l] < data[parentIndex])
      minIndex = l;
    if (r < K && data[r] < data[minIndex])
      minIndex = r;
    //如果minIndex没有发生变化，说明父节点已经是最小了，不用继续调整
    if (minIndex == parentIndex)
      break;

    swap(data, parentIndex, minIndex);
    parentIndex = minIndex;
  }
}

private static void swap (int[] arr, int l, int r) {
  int temp = arr[l];
  arr[l] = arr[r];
  arr[r] = temp;
}

复杂度分析

• 时间复杂度：$O(Nlogk)$O(Nlogk)，buildHeap 时间复杂度为 $O(k)$O(k)；遍历剩下元素并且堆化的时间复杂度为 $(N-k) × O(logk)$(N−k)×O(logk)，故总体的时间复杂度为：$O(Nlogk)$O(Nlogk)。
• 空间复杂度：$O(1)$O(1)，

---

方法三：排序

先对数组进行升序排列，倒数第 k 个元素就是第 k 个最大元素。

/**
 * @date: 2/20/2020 10:12 AM
 * @Execution info：2ms 击败 96.72% 的j，MB 击败 5% 的j
 */
public int findKthLargest2(int[] nums, int k) {
  Arrays.sort(nums);
  return nums[nums.length - k];
}

复杂度分析

• 时间复杂度：$O(N × logN)$O(N×logN)，N 为 nums 的元素个数。
• 空间复杂度：$O(1)$O(1)，原地排序。

---

方法二：分割数组（参考算法）

快速排序为了实现划分，沿着数组移动，将每个元素与枢轴 pivot 进行比较，每一次划分会出现以下情况：

• 索引在区间 $[0, j-1]$[0,j−1] 中的所有元素 <= nums[j]；
• 索引在区间 $[j+1, N-1]$[j+1,N−1] 中的所有元素都 >= nums[j].
• 因为我无需保证所有元素都是有序的，这样做是比快排要高效地多的。

这就是「分而治之」思想的特例 「减而治之」。即：每经过一次这样操作就能缩小排序的范围。 参考了一下别人的精美图：

以 $[5,2,4,1,3,6,0]$[5,2,4,1,3,6,0] 例子：

• 只要是比 pivot 小，循环内部的交换循环都是无作用的。第一个比 pivot 大的值的下标为 5 (nums[5] = 6)，退出循环后，

---