algorithm - 可以处理这些查询的算法

Question

查询类型 1:询问多重集中第 k 个不太频繁(较少出现)的数字。当有多个可能的答案时，返回最大的一个。

对于多重集 = {1, 2, 2, 2, 3, 3} 和 k = 3，答案是 2。

频率(1)= 1，频率(3)= 2，频率(2)= 3；所以第 3 个较少出现的是 2。

查询类型 2:向多重集添加一个整数 x。

查询类型 3:从多重集中删除整数 x。

查询类型 1 是最频繁的查询。

我需要一种算法来处理这些查询，其复杂度优于或等于每个查询的 O(sqrt N)，其中 N 是多重集的当前大小。

Answer 1

首先，我们可以获取一个哈希表并存储每个数字的频率。然后我们需要一个自平衡搜索树，它有一对 (frequency(number), number) 形式的键。

查询 1. 在 O(log(n)) 的自平衡搜索树中搜索第 k 个元素。
查询 2 和 3。在 O(1) 中更改哈希表中的频率，然后在 O(log( n)).