-1

输入:一组元素的连续流及其计数,我的意思是设置为 ADT 而不是 python 集,加上一个 minCount 变量

例如{'a': 3, 'b':1, 'c':2}, minCount = 3

我将得到 n 这样的一组元素及其计数。minCount 对于所有集合都是静态的。

我想要做的是有一个数据结构,我可以在其中随着元素数量的增加移动元素。

假设 minCount 是 3。那么当我得到第一个示例时, a 将出现在一个列表中A,因为它满足 minCount 条件,而 b 和 c 不存在并且存在于 list 中B。现在如果下一组计数是

{'a' : 1, 'b' : 2, 'c': 2, 'd':1}

那么 a 不受影响,因为它的总计数是 4,但 b 和 c 都超过了 3,所以第一个列表A将有 a,b,c 及其总计数。d 将在列表中B。显然,我可以通过两个列表轻松做到这一点。另一种方法是获取所有元素及其计数,然后对其进行传递以获取满足 minCount 的元素。

有没有比我描述的更好的方法来做到这一点?我不需要大概的答案。

4

1 回答 1

0

2 hash tables seems like the best way to go - one for elements below and one for elements above (and equal to) minCount.

Given that hash tables have O(1) expected insert / lookup / update / delete cost, you can't, asymptotically, do much better than that.

于 2013-10-15T21:41:48.850 回答