假设我有三个数组-['a', 'b']和. 如果我要创建第四个数组，该数组与这三个数组相交，并且元素数量最少，那么我得到的数组将是. 我的问题是......我将如何找到这个数组？['b', 'c']['d']['b', 'd']
就像['a', 'b', 'c', 'd']肯定与所有数组相交，但它不是最小的相交 -['b', 'd']是。
有任何想法吗？
问问题
133 次
2 回答
3
我对算法没有一个好的答案，但确实，就像评论者 Amit 所写的那样，这是一个 NP 完全问题。这个问题称为命中集问题，相当于集覆盖问题。
如果您对近似值满意，那么根据 wiki 文章，贪婪地选择命中最多数组的元素，使其尽可能好。
于 2015-07-23T22:13:49.413 回答
1
我认为您可能想要尝试的是遍历每个数组以获取与多个数组匹配的值。然后，一旦你有了这些值，确定你可以从数组中删除哪些值。
例子：
[1,2] [2,3] [2,4] [1,5] [3,7] [4,8]
循环之后，我们发现[1,2,3,4]所有的值都在多个数组中匹配。
现在我们必须确定是否有任何值可以从这个列表中删除。
如果我们消除1，一切还会匹配吗？
不，我们需要1。
如果我们消除2，一切还会匹配吗？
是的，我们可以2从数组中消除。现在我们有了[1,3,4].
如果我们消除3，一切还会匹配吗？
不，我们需要3。
如果我们消除4，一切还会匹配吗？
不，我们需要4。
我们的最终数组是[1,3,4].
如果您有一个完全唯一的数组，这将不起作用。为了解决这个问题，您可以创建一个包含所有假值的布尔数组，并在匹配数组时将值设置为真。任何最终仍然为假的值，您必须从该数组中选择一个值。
于 2015-07-23T22:05:03.283 回答