假设我们有一个Python嵌套列表，里面全是数字，比如 lists = [ [1, 2], [2, 1], [3, 4] ]。现在我需要从中提取出所有唯一的子列表——这里的“重复”定义是：如果一个子列表能通过重排元素得到另一个，那它们就算重复，比如 [2, 1] 和 [1, 2] 就属于重复项。对于上面的输入，输出可以是 [ [1, 2], [3, 4] ]，子列表的顺序或者子列表内部元素的顺序（比如用 [4, 3] 代替 [3, 4]）都算正确输出。

我目前想到的解法思路是这样的：

1. 先把输入里的每一个子列表排序；
2. 把排序后的子列表转成元组（因为列表不可哈希，没法直接放进集合去重）；
3. 用集合自动过滤掉重复的元组；
4. 最后把去重后的元组再转回列表。

时间复杂度分析 #

给所有子列表排序的时间是 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)

备注：内容来源于stack exchange，提问作者ariko stephen