散列100个不同范围的值10亿

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中使用地图，但他希望他实现我自己的数据结构。然后，我建议对每个元素使用排序后的插入，就像在二叉搜索树中一样，但这会给O（nlogn）带来时间复杂度。他想要一个O（n）解决方案。我试图想到任何哈希函数，但我不能想出任何这样的功能。我也尝试过考虑数据结构，但是我必须再次扫描每个数字的每个数字，从而再次给出O（nlogn）的复杂性。什么可能是解决这个问题的可能方法？

Answer 1

哈希表不能保证O（n * k）的理论复杂性。但制作这样的作品很容易。首先，我们需要对价值概率分布做一些假设 - 让它是统一的（否则我们需要一些专门的散列函数）。接下来，让我们选择哈希表大小，比如201条目（所以它会少于50％满）。

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

然后使用具有201个条目对的开放寻址散列表H []：A [i]或NULL;频率值。

Answer 2

我认为散列表是一个很好的解决方案，但我想象一下面试官希望你建立自己的散列表。

这是我在Python中提出的解决方案。我使用mod 100作为我的散列函数，并使用Separate chaining来处理冲突。

import random 

N = random.randint(1, 10**6) 
K = 100 
HASH_TABLE_SIZE = 100 

distinct = [random.randint(1, 10**12) for _ in range(K)] 
numbers = [random.choice(distinct) for _ in range(N)] 

hash_table = [[] for _ in range(HASH_TABLE_SIZE)] 

def hash(n): 
    hash_key = n % HASH_TABLE_SIZE 
    bucket = hash_table[hash_key] 
    for value in bucket: 
     if value[0] == n: 
      value[1] += 1 
      return 
    bucket.append([n, 1]) 

for number in numbers: 
    hash(number) 

for bucket in hash_table: 
    for value in bucket: 
     print('{}: {}'.format(*value)) 

EDIT

解读码的位：

我的哈希表是一个100个元素的数组。数组中的每个条目都是(number, count)条目的列表。为了散列一个数字，我取其模值为100来查找数组中的索引。我扫描那个桶中的数字，如果它们中的任何一个匹配当前的数字，我会增加它的数量。如果我没有找到多少，我追加了新的条目的数量和1

视觉上的初始计列表中，数组看起来有点像这样：

[ 
    [ [0, 3], [34500, 1] ] 
    [ [101, 1] ], 
    [], 
    [ [1502, 1] ], 
    ... 
] 

注意在索引n，存储在桶中的每个值等于n（mod 100）。平均而言，每个存储桶只有一个值，因为阵列中有多达100个不同的值和100个元素。

要打印出最终计数，只需要遍历数组和每个桶中的每个条目并打印出来。

EDIT 2

这里有一个稍微不同的实现，它使用Open addressing与线性探测来代替。我想我其实更喜欢这种方法。

hash_table = [None] * HASH_TABLE_SIZE 

def hash(n): 
    hash_key = n % HASH_TABLE_SIZE 

    while hash_table[hash_key] is not None and hash_table[hash_key][0] != n: 
     hash_key = (hash_key + 1) % HASH_TABLE_SIZE 

    if hash_table[hash_key] is None: 
     hash_table[hash_key] = [n, 1] 
    else: 
     hash_table[hash_key][1] += 1 

for number in numbers: 
    hash(number) 

for entry in hash_table: 
    print('{}: {}'.format(*entry)) 

注：此代码将失败如果确实有超过100个不同的数字。 （它会永远挂起，试图在数组中找到一个开放的位置）。保持检测到这种状态（例如，一旦你走完了数组中的整圈）并引发异常将会很好。

Answer 3

其实，你错了，这个trie会给你O(N)的复杂性。

一个trie的插入/查找/擦除操作需要O(L)时间，其中L是推送到此trie中的字符串的长度。幸运的是，您只需插入不超过1万亿的数字，这意味着L不会大于log(10^12)（对数基数取决于您在此使用的计数系统，我个人会选择256或65536，具体取决于整个系统的哪一部分这个结构是否会起作用）。

总结起来，你需要O(N) * O(log(10^12))等于O(N)的定义为O()。