P59. 数组中第 K 大的元素

https://algocasts.io/episodes/vkmelbWb

這題在 LeetCode 的難度是 easy,不是中等哦。

不過 golang 沒有提供 Heap 要自己實現變比較複雜…

嗯。有些题目的难度定义和 LeetCode 是不一样的。我会自己再判断一下难度。

原來如此,難怪有好幾道難度跟 leetcode 不一致

之前快排中的视频使用的这个代码,相比于这个视频的partition函数,是不是交换次数更少一些呢

  private int hoarePartition(int[] arr, int low, int high) {
    int pivot = arr[low + (high-low)/2];
    int i = low, j = high;
    while (true) {
      while (arr[i] < pivot) ++i;
      while (arr[j] > pivot) --j;
      if (i >= j) return j;
      swap(arr, i++, j--);
    }
  }

@11

是的。hoarePartition 中两边都移动完,才进行一次交换;而 P59 中使用的这个 partition 函数(见下面代码)是一边移动完,就做一次交换。所以 hoarePartition 的交换次数是要更少的。(我简单做了个不严谨的测试,对于均匀分布的随机序列,长度从 1000 ~ 5000。交换次数会少 50% ~ 70%

  private int partition(int[] nums, int low, int high) {
    int pivot = nums[low], i = low, j = high;
    while (i < j) {
      while (i < j && nums[j] < pivot) --j;
      if (i < j) swap(nums, i, j);
      while (i < j && nums[i] >= pivot) ++i;
      if (i < j) swap(nums, i, j);
    }
    return i;
  }

不过,上述的 partition 函数做了些改造,使得最后 pivot 正好移动到分割成两半子序列的中间,并且返回的下标 i 指向的就是 pivot。这样做有两个好处:

  • 在下一轮排序中,就可以不管下标 i 那个位置,因为它指向 pivot,已经在正确的位置上。
  • 线性求第 K 大中,如果返回的下标 i 等于 k-1,那下标 i 指向的就是第 K 大的数字。hoarePartition 无论做这种保证。