#include <iostream>#include <unordered_map>#include <algorithm>#include <vector>using namespace std;const int MAXN = 100010;int n;int op[MAXN];int x[MAXN];int cnt[MAXN];int bucket[MAXN];int maxCnt, maxNum;unordered_map<int, int> mp;int main() { while (cin >> n) { mp.clear(); fill(cnt, cnt + MAXN, 0); fill(bucket, bucket + MAXN, 0); maxCnt = 0, maxNum = 0; for (int i = 1; i <= n; i++) { cin >> op[i] >> x[i]; if (op[i] == 1) { mp[x[i]]++; cnt[mp[x[i]]]++; maxCnt = max(maxCnt, mp[x[i]]); } } for (auto p : mp) { int num = p.first, c = p.second; if (c == maxCnt) { bucket[c]++; maxNum = max(maxNum, num); } else if (c > 0) { bucket[c]++; } } for (int i = maxCnt - 1; i >= 0; i--) { bucket[i] += bucket[i + 1]; } for (int i = 1; i <= n; i++) { if (op[i] == 2) { if (bucket[x[i]] == 0) { cout << maxNum << endl; } else { int k = min(bucket[x[i]], cnt[x[i]]); for (auto p : mp) { if (p.second == x[i]) { if (k == 1) { cout << p.first << endl; break; } else { k--; } } } } } } } return 0;}解释一下上述代码
时间: 2024-02-10 07:33:27 浏览: 21
这段代码实现了一个查询系统,可以查询出最常出现的数字以及该数字在输入序列中最靠后出现的位置。具体来说,程序首先读入一个整型数 n,表示接下来要输入的操作数。然后,程序开始进行 n 次操作,每次操作会读入一个操作类型 op 和一个整数 x。如果 op 为 1,则表示要将 x 加入到输入序列中;如果 op 为 2,则表示要查询序列中第 x 个最常出现的数字,并输出该数字在序列中最靠后出现的位置。
程序的实现中,使用了两个数组 cnt 和 bucket,分别用于统计每个数字出现的次数以及每个出现次数的数字个数。具体来说,每次加入一个新的数字 x 时,就将其在哈希表中出现次数加 1,并将 cnt[x] 加 1。然后,将 maxCnt 更新为所有数字中出现次数最大的值。在统计完所有数字的出现次数之后,程序会遍历所有数字,将出现次数相同的数字放在一个桶中,并将桶的大小存储在 bucket 数组中。接着,程序会从后往前遍历 bucket 数组,将后面的桶大小加到前面的桶上,这样可以方便地确定出现次数不小于某个数的数字个数。
最后,程序会再次遍历所有操作,对于每个查询操作,根据 bucket 数组和 cnt 数组可以确定出现次数为 x 的数字个数 k。然后,程序会遍历哈希表,找到出现次数为 x 的数字,并将 k 不断减 1,直到 k 等于 1,此时找到了第 x 个最常出现的数字,并输出其在序列中最靠后出现的位置。如果 k 减到 0 还没有找到,则输出出现次数最大的数字。
相关问题
#include <iostream> #include <vector> #include <algorithm>
#include <iostream> 是C++中的一个头文件,它包含了输入输出流的相关函数和对象,例如cout和cin。通过包含这个头文件,我们可以在程序中使用标准输入输出流来进行输入和输出操作。
#include <vector> 是C++中的一个头文件,它定义了一个名为vector的容器类模板。vector是一个动态数组,可以存储不同类型的元素,并且可以根据需要动态调整大小。
#include <algorithm> 是C++中的一个头文件,它包含了一些常用的算法函数,例如排序、查找、替换等。通过包含这个头文件,我们可以在程序中使用这些算法函数来对容器中的元素进行操作。
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。