假设S是一组数组，我们想找到出现在中的每个数组中的值的最大子集S。值可能会出现多次，如果一个值x在每个数组中至少出现一次，则它应该x在输出集中出现次数。
这个问题可以看作是找到的内核S。
为了进行复杂度计算，假定S包含n数组，所有数组都为size m。
例：
A = {4, 3, 8, 12, 5, 4, 4, 4}
B = {5, 4, 12, 1, 1, 4, 1, 1}
C = {2, 11, 4, 8, 4, 5, 2, 8}
Answer = {4, 4, 5} // order doesn't matter
一些注意事项：
S，则它将输入答案。{4, 5}），则可以对每个数组使用哈希表来检查是否已经将值添加到“大”哈希表中（从上一个项目符号开始），以防止重复插入数组中出现多次的值（或防止重复插入的任何其他措施）。对执行此任务的有效（时间和内存）算法有何建议？
创建count第一个数组的值的哈希表。
对于哈希表中的每个条目，还存储一个total，应将其设置为与计数相同。
对于每个下一个数组：
重置哈希表中每个元素的计数。
遍历数组，在哈希表中设置计数。
为哈希表中的每个条目设置total = min(count, total)
（用删除条目total = 0）
复杂：
O(n)空间和（预期的）时间复杂度，其中n元素的总数。
对每个数组进行堆处理（到min-heap）（也可以与排序一起使用，但是这种解释有点令人困惑）。
max=每个堆的最小值中的最大值，并且maxIndex=该堆的索引。maxIndex + 1换行开始循环遍历堆，直到用完所有值。
maxIndex，这意味着所有值都相同，因此输出最后弹出的值。> max，集max并maxIndex适当地或（效率略低）：
对所有数组进行排序。
复杂：
O(m)空间和O(m n log n)时间复杂度，其中m是数组数，n是每个数组中元素的平均数。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句