Top-k问题

简介

在一堆数中求其第k大或第k小的问题，简称TOP-K问题，目前最有效的算法是“BFPRT算法”

背景介绍

在一堆数中求其第k大或第k小的问题，简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是”BFPRT算法”，又称为”中位数的中位数算法”，该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出，最坏时间复杂度为$O(n)$。

在首次接触TOP-K问题时，我们的第一反应就是可以先对所有数据进行一次排序，然后取其前k即可，但是这么做有两个问题：

快速排序的平均复杂度为$O(nlogn)$，但最坏时间复杂度为$O(n^2)$，不能始终保证较好的复杂度。

我们只需要前k大的，而对其余不需要的数也进行了排序，浪费了大量排序时间。

除这种方法之外，堆排序也是一个比较好的选择，可以维护一个大小为k的堆，时间复杂度为$O(nlogk)$。

那是否还存在更有效的方法呢？受到快速排序的启发，通过修改快速排序中主元的选取方法可以降低快速排序在最坏情况下的时间复杂度，并且我们的目的只是求出前k，故递归的规模变小，速度也随之提高。

下面来简单回顾下快速排序的过程，以升序为例：

  • 选取主元（数组中随机一个元素）
  • 以选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边
  • 分别对左边和右边进行递归，重复上述过程

BFPRT算法过程及代码

BFPRT算法步骤如下：
（1）：选取主元
（1.1）：将n个元素划分为$\frac{n}{5}$个组，每组5个元素，若有剩余，舍去
（1.2）：使用插入排序找到$\frac{n}{5}$个组中每一组的中位数
（1.3）：对于（1.2）中找到的所有中位数，调用BFPRT算法求出它们的中位数，作为主元
（2）：以（1.3）选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边
（3）：判断主元的位置与k的大小，有选择的对左边或右边递归。

上面的描述可能并不易理解，先看下面这幅图：

BFPRT( ) 调用 GetPivotIndex( ) 和 Partition( ) 来求解第k小，在这过程中，GetPivotIndex () 也调用了 BFPRT()，即 GetPivotIndex( ) 和 BFPRT( ) 为互递归的关系。

下面为代码实现，其所求为第k小的数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
int s[100010], n, k;
/* 插入排序，返回中位数下标 */
int InsertSort(int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int temp = s[i], place = i - 1;
        while (place >= left && s[place] > temp)
            s[place + 1] = s[place --];
        s[place + 1] = temp;
    }
    return ((right - left) >> 1) + left;
}
/* 返回中位数的中位数下标 */
int BFPRT(int left, int right, const int &k);
int GetPivotIndex(int left, int right) {
    if (right - left < 5) return InsertSort(left, right);
    int sub_right = left - 1;
    for (int i = left; i + 4 <= right; i += 5) {
        int index = InsertSort(i, i + 4); // 找到五个元素的中位数小标
        swap(s[++sub_right], s[index]); // 依次放在左侧
    }
    return BFPRT(left, sub_right, ((sub_right - left + 1) >> 1) + 1);
}
/* 利用中位数的中位数的下标进行划分，返回分界线下标 */
int Partition(int left, int right, int pivot_index) {
    swap(s[pivot_index], s[right]);
    int divide_index = left;
    for (int i = left; i < right; ++i) 
        if (s[i] < s[right])
            swap(s[divide_index++], s[i]);
    swap(s[divide_index], s[right]);
    return divide_index;
}
int BFPRT(int left, int right, const int &k) {
    int pivot_index = GetPivotIndex(left, right); // 得到中位数的中位数下标
    int divide_index = Partition(left, right, pivot_index); // 进行划分，返回划分边界
    int num = divide_index - left + 1;
    if (num == k) return divide_index;
    else if (num > k) return BFPRT(left, divide_index - 1, k);
    else return BFPRT(divide_index + 1, right, k - num);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &s[i]);
    printf("%d\n", s[BFPRT(0, n - 1, k)]); // 第k小值
    return 0;
}

时间复杂度分析

参考文章: 算法爱好者

文章目录
  1. 1. 简介
  2. 2. 背景介绍
  3. 3. BFPRT算法过程及代码
  4. 4. 下面为代码实现，其所求为第k小的数：
  5. 5. 时间复杂度分析
,