-3

我们有一个包含整数的数组,我想在这个数组中找到重复 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) 以及空间容量是必需的。

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

4

1 回答 1

0

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) 的各个值。

于 2013-02-15T16:02:34.903 回答