algorithm - 在未排序的数组中查找重复 k 次的数字

Question

我们有一个包含整数的数组，我想在这个数组中找到重复 k 次的数字。数组未排序，数字无界。

例子，

A(20, 6, 99, 3, 6, 2, 1,11,41, 31, 99, 6, 7, 8, 99, 10, 99, ,6)

找出重复超过 3 次的数字。

答案：6,99

使用按位运算（xor）或组合的可能答案？运行时间效率 Big(o) 以及空间容量是必需的。

这不是家庭作业，它只是一个有趣的问题。

Answer 1

Patrick87 可能在评论中给出了最直接的答案，所以我将给出另一种方法。

当您遍历您的列表时，您将创建一个元素（id，值）并将其插入到地图中，其中 id 等于数字，并且该值与插入时初始化为 1 的计数匹配。如果该值已存在于地图中，则只需递增计数器。

插入地图将花费 O(log k) 时间，其中 k 是地图的大小。因此，您的地图创建总时间为 O(n log n)。

创建映射后，您可以对其进行迭代，并输出 count == target count 的任何数字。

时间复杂度 = O(n) + O(n log n) + O(n) = O(n log n) 空间复杂度 = O(n) + O(n) = O(n)

如果您正在寻找更好的空间复杂度，那么您将不会得到它......即使数字是从流中读取的，您也需要跟踪 O(n) 的各个值。