arrays - 找到数组中出现 m 次的唯一整数

Question

此数组中所有其他整数出现 n 次的位置。我们有 n>m。 该数组中的所有元素都是整数。您能否设计一个在 O(N) 中运行的算法，其中 N 是数组中元素的数量，同时最小化空间复杂度？在最好的情况下，空间复杂度可以限制为 O(log(m))。

一个特例是 n=2 和 m=1(这很简单)。是否存在可以处理任意 m 和 n 的通用算法？

谢谢

Answer 1

您可以使用哈希表将数组中的数字映射到出现的次数。您可以遍历数组，增加每个数字的出现次数。然后，您可以遍历哈希表，搜索出现 n 次的键。