algorithm - 我需要一种算法来查看 3 个列表并找到独特的项目

Question

我已经摸不着头脑几个小时了，需要一些帮助...

我有 3 个对象列表。每个列表可以包含相同的对象(但不是必须)。我想要一种算法来测试每个列表中是否至少有一个唯一对象。

编辑:一个项目只能在每个列表中出现一次，但可以在多个列表中。

编辑:有一个伪第 4 个列表 - 3 个列表中的每一个都有 1 个项目。这是必须包含唯一性的列表。总共可能有 3 个项目，每个列表中都有每个项目。这应该返回 true，因为第 4 个列表可能包含唯一值。

编辑:这是我到目前为止想到的，但我不知道它的效率如何，甚至不知道它是否有效!

bool Uniques( List<Item> list1, List<Item> list2, List<Item> list3 ) {
    foreach( Item item1 in list1 ) {
        foreach( Item item2 in list2 ) {
            if ( item1!=item2 ) {
                foreach( Item item3 in list3 ) {
                    if ( item3!=item1 && item3!=item2 ) return true;
                }
            }
        }
    }
    return false;
}

编辑:为了说明，这里有一个例子。
从整体颜色列表中:红色、绿色、蓝色、黄色、青色、品红色、白色、黑色、橙色、紫色。

列表 1 包含红色、绿色
list 2 包含红色
list 3 包含蓝色、橙色
结果为假

列表 1 包含红色、绿色
list 2 包含红色、绿色
list 3 包含红色、绿色
结果为假

列表 1 包含红色、绿色
list 2 包含黄色
list 3 包含红色、绿色
结果为真

Answer 1

编辑:由于对原始问题的误解，我实际上是在更改我的答案。

既然我们知道每个列表元素在它的列表中都是唯一的，那么我们可以使用下面的算法:

Compute the length of the three lists.
Sort these lengths into a tuple (l_1,l_2,l_3) in ascending order.

If l_1 >= 1 and l_2 >= 2 and l_3 >= 3, then answer 'YES'; 
else, 
    if among all possible combinations there is a valid one, 
    then, return 'YES', 
    otherwise return 'NO'. 

如果您事先知道列表的长度(否则它是线性的)，则此算法需要常数时间。请注意，在检查所有可能组合的情况下，您检查的三元组少于 6 个。

现在，这个有效的证明非常简单:从长度为 l_1 的列表中选择一个元素 x_1，然后选择一个元素 x_2 来自长度为 l_2 的列表，与 x_1 不同(这是可能的，因为 l_2 >= 2)。现在，从长度为 l_3 的列表中选择一个元素 x_3，不同于 x_1 和 x_2。同样，您可以选择这样的元素，因为该列表至少包含三个不同的元素。

我希望现在我真的解决了你所要求的问题。