0

我一直在挠头几个小时，可以使用一些帮助......

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

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

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

4

3 回答 3

2

编辑：由于对原始问题的误解，我基本上改变了我的答案。

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

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从长度列表中l_1选择一个元素，然后x_2从长度列表中选择一个元素l_2，不同于x_1（这是可能的l_2 >= 2）。x_3现在，从长度列表中选择一个与和l_3不同的元素。同样，您可以选择这样一个元素，因为该列表至少包含三个不同的元素。x_1x_2

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

于 2013-02-04T21:20:47.437 回答
0

线性时间：使用哈希。首先将列表 1 的每个 elt 散列为三个布尔值的数组，将第一个布尔值设置为 true。对列表 2 和 3 重复此操作。瞧——您有一个散列，其键是元素，其值指示每个元素属于哪个列表。

然后，要查看每个列表中是否至少有一个唯一项，循环遍历哈希值，检查三个布尔值中只有一个设置为 true 的数组。例如，如果一个值为 [true, true, false] 你忽略它，但如果一个值为 [false, true, false] 那么你知道第二个列表有一个唯一的项目。

于 2013-02-04T21:09:24.470 回答
0 
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

当且仅当每个列表包含不在任何其他列表中的值时，返回的列表才会为非空。如果它是空的，它就是这样的非共享值的集合。

于 2013-02-04T22:07:51.767 回答