我们有一个包含整数的数组,我想在这个数组中找到重复 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) 以及空间容量是必需的。
这不是家庭作业,它只是一个有趣的问题。
我们有一个包含整数的数组,我想在这个数组中找到重复 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) 以及空间容量是必需的。
这不是家庭作业,它只是一个有趣的问题。
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) 的各个值。