3

假设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}是防止重复插入在数组中出现多次的值（或任何其他防止重复插入的方法）。

对执行此任务的有效（时间和内存）算法有什么建议吗？

4

2 回答 2

3

基于散列的方法

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

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

对于每个下一个数组：

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

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

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

复杂：

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

基于排序的方法

Heapify 每个数组（到一个 min-heap）（也可以用于排序，但这种解释有点令人困惑）。

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

或者（效率稍低）：

对所有数组进行排序。

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

复杂：

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

于 2013-11-06T14:42:04.593 回答
0
  • 将集合编码为素数的乘积
  • 计算公共子集作为结果数字的 GCD
  • 分解生成的 GCD 以显示常见项目。
  • 这当然受到项目数量和集合大小的限制（否则素数的乘积可能会溢出）
#include <stdio.h>
#include <string.h>

unsigned primes [] = { 2,3,5,7,11,13,17, 19, 23, 29,31,37,41,43,47};
unsigned value(unsigned array[], unsigned count);
unsigned gcd(unsigned a, unsigned b);
unsigned factorise(unsigned result[], unsigned val);


unsigned value(unsigned array[], unsigned count)
{
unsigned val, idx;

val = 1;
for (idx = 0; idx < count; idx++) {
        val *= primes [ array[idx]];
        }

return val;
}

unsigned gcd(unsigned a, unsigned b)
{
if (b > a) return gcd (b, a);
if (b <= 1) return a;
if (b == a) return a;
return gcd (b, a-b);
}

unsigned factorise(unsigned result[], unsigned val)
{
unsigned idx, count;

for (count=idx=0; val > 1; ) { 
        if ( val % primes[idx] ) idx++;
        else {
                result[count++] = idx;
                val /= primes[idx];
                }
        }
return count;
}

int main(void)
{
unsigned one[]  = {4, 3, 8, 12, 5, 4, 4, 4};
unsigned two[]  = {5, 4, 12, 1, 1, 4, 1, 1};
unsigned three[]  = {2, 11, 4, 8, 4, 5, 2, 8};
unsigned result[12]  , count, idx;;

unsigned val1, val2,val3
        , gcd12 , gcd23 , gcd13, gcd123;

val1 = value(one, 8);
val2 = value(two, 8);
val3 = value(three, 8);

gcd12 = gcd(val1,val2);
gcd23 = gcd(val2,val3);
gcd13 = gcd(val1,val3);
gcd123 = gcd(gcd12,gcd23);

fprintf(stdout, "Val1=%u, Val2=%u Val3=%u gcd= [%u %u %u]: %u\n"
        , val1, val2, val3
        , gcd12 , gcd23 , gcd13, gcd123);

count = factorise( result, gcd123);

for (idx=0; idx < count; idx++) {
        fprintf(stdout, "%c %u", idx? ',' : '{', result[idx] );
        }
fprintf(stdout, "}\n" );

return 0;
}

这是基于我在这里的回答。

于 2013-11-06T17:14:25.487 回答