c - C 中 n 数组的交集算法

Question

我需要编写一个函数，返回查询数组的每次迭代中生成的所有数组的交集(AND条件)。

如果我的查询是这样给出的: query[] = {"num>20", "avg==5", "deviation != 0.5"} 那么，n 从 0 运行到 查询长度。查询被传递到一个函数 (get_sample_ids)，该函数将条件与拥有特定信息的样本列表进行比较。 get_sample_ids 返回的数组编号是各个样本的索引。

query[] = {"num>20", "avg==5", "deviation != 0.5"}
int intersected_array*;
for n=0:query.length-1
    int arr* = get_sample_ids(query[n]);
    // n=0: [1, 7, 4, 2, 6]
    // n=1: [3, 6, 2]
    // n=2: [6, 2]
end;

Expected output: intersected_array* = [6, 2]

我编写了一个具有 2 个数组的实现(arr*、temp*)。对于迭代中返回的每个数组，它首先存储在 temp* 数组中，而 arr* 和 temp* 的交集存储在arr*。这是最佳解决方案还是最好的方法是什么？

Answer 1

这非常有效，但实现起来可能很麻烦(还没有尝试过)。

1. 确定shortest大批。使用 C 的好处是，如果您不知道它们的长度，可以使用指向数组的指针来确定它们是否按顺序放置在内存中。
2. 创建 <entry,boolean>哈希map对于 shortest 中的条目。我们知道规模，如果有的话，也只会在接下来的步骤中缩小。
3. 迭代数组。首先启动整个map为假。对于每个条目，请检查 map .
4. 迭代map删除所有未检查的条目。将所有值设置为 false。
5. 如果还有任何新数组，请返回到步骤3。并使用新数组。
6. 结果就是最终map中的键.

看起来很多，但我们不必采取任何高复杂性的措施。良好性能的关键是使用 HashMap ，因为访问时间恒定。

或者:

制作map是<entry,int> 。这样您就可以计算所有重复次数，而不必在每次迭代时重置它，这会增加复杂性。

最后只需将数组的数量与 map 中的值进行比较即可。那些匹配的就是您的解决方案。

复杂性:

看起来像 O(n)。