c++ - 散列范围为 10 亿的 100 个不同的值

Question

我最近在一次采访中被问到这个问题。我有一个包含 n 个元素的数组。该数组只有 100 个不同的值。我需要打印每个数字的出现次数。

 1<=n<=10^6
 1<=A[i]<=10^12

预期的空间复杂度为 O(k)，其中 k 是数组中不同值的数量。

例如，1 2 3 2 1 4 3 2 4 2 3 1 2；这里 k 是 4。 首先我建议在 STL 中使用 map ，但他希望他实现我自己的数据结构。然后我建议对每个元素使用排序插入，就像在二叉搜索树中一样，但这会产生 O(nlogn) 的时间复杂度。他想要一个 O(n) 的解决方案。我试图想出任何哈希函数，但我想不出任何这样的函数。我也尝试考虑 trie 数据结构，但我将不得不再次扫描每个数字的每个数字，从而再次给出 O(nlogn) 复杂性。解决这个问题的可能方法是什么？

Answer 1

哈希表不能保证 O(n*k) 的理论复杂度。但是制作这样的一个很容易。

首先，我们需要对值概率分布做出一些假设 - 让它是均匀的(否则我们需要一些专门的哈希函数)。

接下来，让我们选择哈希表的大小，比如 201 个条目(这样它的填充率将低于 50%)。

接下来，让哈希函数只是 hash(A[i]) = A[i] mod 201。

然后使用具有 201 个条目对的开放寻址哈希表 H[]:A[i] 或 NULL；频率值。