arrays - 查找一组数组的最大子集(内核)的算法

Question

令S 为一组数组，我们要找到出现在S 中每个数组中的值的最大子集。值可能会出现多次，如果一个值在每个数组中至少出现 x 次，则它应该在输出集中出现 x 次。

这个问题可以看作是寻找S的内核。

为了计算的复杂性，假设S包含n个数组，它们的大小都是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})，我们可以为每个数组使用哈希表来检查值是否是已经添加到“大”哈希表(来自上一个项目符号)以防止重复插入在数组中出现多次的值(或任何其他防止重复插入的方法)。

对执行此任务的高效(时间和内存)算法有何建议？

Answer 1

基于哈希的方法

为第一个数组的 count 创建一个哈希表。

对于哈希表中的每个条目，还存储一个总数，应该设置为与计数相同。

对于每个下一个数组:

• 重置哈希表中每个元素的计数。

• 遍历数组，在哈希表中设置计数。

• 对于哈希表中的每个条目，设置total = min(count, total)
  (删除 total = 0 的条目)

复杂性:

O(n) 空间和(预期)时间复杂度，其中 n 是元素的总数。

基于排序的方法

堆化每个数组(到 a min-heap )(也可以用于排序，但这个解释有点令人困惑)。

• 设 max = 每个堆的最小值中的最大值，maxIndex = 该堆的索引。
• 从 maxIndex + 1 开始循环遍历堆，直到我们用完所有值。
  • 如果我们一直回到 maxIndex，这意味着所有值都相同，所以输出最后弹出的值。
  • 如果当前堆的最小值为> max，适当设置max和maxIndex
    (但不要删除最小值)。
  • 否则从当前堆中删除最小值。

或者(效率稍低):

对所有数组进行排序。

• 保留 binary search tree所有当前元素的 (BST)(初始化为包含每个数组的第一个元素)。
• 重复从 BST 中删除最小值，并从删除元素所在的数组中添加下一个元素。
• 每当 BST 的最小值和最大值相同时，所有节点都相等，因此我们输出该值。
• 为了处理重复项，我们需要记录自上次输出值以来添加了多少元素。仅当该计数大于或等于数组数时才输出一个值。

复杂性:

O(m) 空间和 O(m n log n) 时间复杂度，其中 m 是数组的数量，n 是每个数组的平均元素数。