求第 k 小元素

线性时间选择

元素选择问题的一般提法:给定线性序集中 n 个元素和一个整数 k1kn,要求找出这 n 个元素中第 k 小的元素。即如果将这个 n 个元素依基线排列时,排在第 k 个位置的元素即为我们所找的元素。

在数组有序的情况下,可以很容易地通过递归的方法找到其中第 k 小元素。

  • 如果 kip+1,则 a[p:r] 的第 k 小元素落在子数组 a[p:i] 中。
  • 如果 k>ip+1,则 k 落在 a[i+1:r] 是其中第 k(ip+1) 小元素。

算法代码

template <class Type>
Type RandomizedSelect(Type a[], int p, int r, int k) {
    if (p == r) {
        return a[p];
    }
    int i = RandomizedPartition(a, p, r);
    j = i - p + 1;
    if (k <= j) {
        return RandomizedSelect(a, p, i, k);
    } else {
        return RandomizedSelect(a, i + 1, r, k - j);
    }
}

算法分析

在最坏情况下,线性时间选择算法需要 O(n2) 的计算时间。但可以证明,线性时间选择算法可以在 O(n) 平均时间内找出 n 个输入元素中的第 k 小元素。

堆排序

现在问题升级,如果数组不是有序的,即在有 n 个元素的数组中找第 k 小的元素。

此问题的解决思路可以先对原始数组进行排序,然后再采用线性时间选择算法求解。这里可以采用堆排序的方法找第 k 小元素。

算法思想

为了找第 k 小元素,需要将数组按照升序排序,因此建立最大堆。循环执行以下步骤,直至所有元素出堆:

  • 每次堆顶元素(即最大元素)与堆中最后一个元素交换。
  • 剔除最大元素后调整为最大堆。

算法分析

  • 调整为最大堆:O(logn)
  • 循环弹出堆顶元素:O(n)

因此堆排序的时间复杂度为 O(nlogn)

最终对排序后的数组进行线性时间选择,时间复杂度为 O(nlogn)。因此,采用堆排序的方法求解第 k 小元素的时间复杂度为 O(nlogn)

复杂度为 O(n) 的算法

设数组 S 的长度为 n。若 n<50,则采用堆排序的方法找出第 k 小元素。否则,

  • n 个元素分为 n/5 组,每组 5 个元素并排序。
  • 将每组的第 3 个元素取出,得到大小为 n/5 的数组 M
  • 在数组 M 中找第 n/5/2 小的元素 m
  • 将原数组 S 分为大于 m、等于 m 和小于 m 的三个集合,并计算集合中元素的个数,并将之与 k 作比较,确定第 k 小元素所在的集合。
Previous
Next