高效的算法，在给定列表列表作为输入的情况下返回唯一列表的列表

Question

给定一个包含数字的列表的python列表，即

lists = [ [1, 2], [2, 1], [3, 4] ]

，问题是从输入列表中返回所有唯一列表的列表。如果一个列表可以通过对列表中的项目重新排序而从另一个列表生成，则该列表被视为重复。即

[2, 1]

是

[1, 2].

的重复项，给定输入

[ [1, 2], [2, 1], [3, 4] ]

，输出应该是

[ [1, 2], [3, 4]]

。

[ [1, 2], [3, 4]] 

的任何重新排序也是正确的，即

[1, 2], [4, 3]],

我的做法是首先对输入列表中的所有列表进行排序，将列表转换为元组，使用集合数据结构过滤掉重复的元组，最后将唯一的元组转换回列表。对所有列表进行排序的时间复杂度为

O(m*nlogn)

，其中 m 是列表的数量，n 是每个列表的大小（假设列表大小相同）。将列表转换为元组需要

O(mn)

时间，从元组创建集合需要

O(mn)

，将唯一元组集合转换回列表也需要

O(mn)

，使得总时间复杂度为 O

(mnlogn + mn + mn + mn) = O(mnlogn)

。

我们还能做得比

O(mnlogn)

更好吗？

代码：

def find_unique(lists):
  sorted_lists = [ sorted(lst) for lst in lists]
  tuples = [tuple(lst) for lst in sorted_lists]
  unique_tuples = set(tuples)
  return list(unique_tuples)

Answer 1

使用一组冻结集：

def unique(lists):
    seen = set()
    result = []
    for sub in lists:
        key = frozenset(sub)
        if key not in seen:
            result.append(sub)
            seen.add(key)
    return result