我已经摸不着头脑几个小时了,需要一些帮助...
我有 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 包含红色、绿色
结果为真
最佳答案
编辑:由于对原始问题的误解,我实际上是在更改我的答案。
既然我们知道每个列表元素在它的列表中都是唯一的,那么我们可以使用下面的算法:
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
。同样,您可以选择这样的元素,因为该列表至少包含三个不同的元素。
我希望现在我真的解决了你所要求的问题。
关于algorithm - 我需要一种算法来查看 3 个列表并找到独特的项目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14695121/