前言

最近听一个学长讲了如何利用比特串求解排名第k位的数据，觉得还挺巧妙的

分析

下面以求解排名第k位和成绩第k小(即倒数排名为k)的学生成绩为例解释算法思路：

  • 录入学生成绩后，将成绩转换为比特串，规则如下：

    定义一个容量为101的整型数组存放比特串并初始化为0，学生成绩为n则数组下标为n的数据置1（0≤n≤100，故数组容量定为101）

    例如：一个容量为6数据为2的数组按上述规则应为{0, 0, 1, 0, 0, 0}

  • 将每个学生成绩的比特串逐列相加，得到一个聚合后的比特串

    例如：{0, 0, 0, 1, 0, 0} 与 {1, 0, 0, 0, 0, 0}聚合后为{1, 0, 0, 1, 0, 0}

  • 要得到排名为k(成绩相同认为排名相同)的学生成绩，只需要定义一个初值为0的sum，从高位下标向低位下标依次加上聚合比特串数组的数据，直到sum ≥ k，对应的下标就是排名为k的学生成绩

  • 同理：要得到第k小的学生成绩，我们可以定义一个初值为0的sum，从低位下标向高位下标依次加上聚合比特串数组的数据，直到sum ≥ k，对应的下标就是第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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
#define N 101   // 采用百分制，0~100共101个数字

int  main()
{
    int n;
    cout << "请输入学生人数: ";
    cin >> n;
    vector<int> grade(n);   // 存放学生成绩
    vector<int> bit(N, 0);  // 初始化学生成绩比特串，并用于后续存放比特聚合后的数据
    vector<vector<int>> bit_grade(n, bit);  // 存放所有学生成绩比特串

    // 录入成绩并转换为比特串
    for (int i = 0; i < n; ++i)
    {
        cout << "请输入第" << i + 1 << "位学生的成绩: ";
        cin >> grade[i];
        assert(grade[i] >= 0 && grade[i] <= 100);
        bit_grade[i][grade[i]] = 1;
    }   

    // 比特聚合，即同列相加
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            bit[i] += bit_grade[j][i];

            // 分数相同归为同一排名
            if (bit[i] > 1)
                bit[i] = 1;
        }
    }

    // 比较
    int k, sum = 0;
    int choice, stop = 1;

    while (stop == 1)
    {
        sum = 0;
        cout << "正向排名请填1, 反向排名请填2: ";
        cin >> choice;

        if (choice == 1)
        {
            cout << "请问您需要排名第几的数据: ";
            cin >> k;
            for (int i = 100; i >= 0; --i)
            {
                if (sum >= k)
                {
                    cout << "排名第" << k << "的数据是: " << i + 1 << endl;
                    break;
                }
                else
                {
                    sum += bit[i];
                }
            }

            cout << "继续请填1, 停止请填2: ";
            cin >> stop;
            cout << endl;
        }
        else
        {
            assert(choice == 2);
            cout << "请问您需要第几小的数据: ";
            cin >> k;
            for (int i = 0; i < 101; ++i)
            {
                if (sum >= k)
                {
                    cout << "第" << k << "小的数据是: " << i - 1 << endl;
                    break;
                }
                else
                {
                    sum += bit[i];
                }
            }

            cout << "继续请填1, 停止请填2: ";
            cin >> stop;
            cout << endl;
        }
    }

    return 0; 
}