我需要一个算法来查看3个列表，并找到唯一的项目

Question

我已经挠头几个小时了，需要一些帮助...

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

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

编辑：有一个伪第四个列表-三个列表中各有一个项目。这是必须包含唯一性的列表。每个列表中总共可能有3个项目。这应该返回true，因为第四个列表可能包含unique。

编辑：这是我到目前为止提出的，但我不知道这有多有效，甚至不知道它是否有效！

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包含红色，绿色
列表2包含红色
列表3包含蓝色，橙色
结果为FALSE

列表1包含红色，绿色
列表2包含红色，绿色
列表3包含红色，绿色
结果为FALSE

列表1包含红色，绿色
列表2包含黄色
列表3包含红色，绿色
结果为TRUE

Answer 1

set counter = 0
create empty list U
for each list L
    create D, a duplicate of list L
    for each list P, where P != L
        remove all items in P from D

    add all items in D to U
    if D is not empty, increment counter


if counter == number of lists, return U, else return empty list

当且仅当每个列表包含不在任何其他列表中的值时，返回的列表将为非空。如果为空，则为此类非共享值的集合。

Answer 2

线性时间：使用散列。首先将列表1的每个elt散列为三个布尔值的数组，将第一个布尔值设置为true。对列表2和3重复上述步骤。瞧，您有一个散列，其键是元素，其值指示每个元素所属的列表。

然后，为了查看每个列表中是否至少有一个唯一的项，循环遍历散列值，检查三个bool中只有一个设置为true的数组。例如，如果一个值为[true，true，false]，则忽略它，但如果一个值为[false，true，false]，则您知道第二个列表具有唯一项。

Answer 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个三元组。

现在，证明这一点的证据非常简单：从长度列表中选择一个元素x_1，然后从长度列表中选择一个元素x_2，不同于x_1（这是可能的，因为l_2

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