查询类型 1: 询问多重集中第 k 个频率较低(出现次数较少)的数字。当有多个可能的答案时，返回最大的一个。
对于多重集 = {1, 2, 2, 2, 3, 3} 且 k = 3，答案为 2。
频率(1) = 1，频率(3) = 2，频率(2) = 3；所以第三个较低的频率是 2。
查询类型 2: 将整数 x 添加到多重集。
查询类型 3: 从多重集中删除整数 x。
查询类型 1 是最常见的查询。
我需要一种能够处理这些查询的算法，其复杂度优于或等于每个查询的 O(sqrt N)，其中 N 是多重集的当前大小。
最佳答案
首先，我们可以使用一个哈希表来存储每个数字的频率。然后我们需要一个自平衡搜索树，其键的形式为一对(频率(数字)，数字)。
查询 1. 在自平衡搜索树中搜索第 k 个元素，时间复杂度为 O(log(n))。
查询 2 和 3。在 O(1) 中更改哈希表中的频率，然后在 O(log( n)).
关于algorithm - 可以处理这些查询的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48457625/