主页 / coding / 问题 / 79249078
Accepted
ariko stephen
Asked: 2024-12-04 04:23:15 +0800 CST

高效算法，给定一个列表列表作为输入，返回一个唯一列表列表

  • 772

给定一个包含数字的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) 使总时间复杂度为(mnlogn + mn + mn + mn) = O(mnlogn)O。

我们还能做得更好吗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)
python

2 个回答

  1. Best Answer

    只要您使用的“密钥”是 O(m*n)，您就可以获得 O(m*n) 解决方案。这可以通过两种方式实现。

    如果内部列表不能包含重复项，那么一组冻结集是一个优雅的解决方案。注意，frozenset(mylist)是 O(n)：

    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

    以上代码返回输入中实际出现的第一个“唯一”列表。如果唯一列表的任何顺序都是有效的，即使是原始输入中未出现的顺序（我假设是这种情况，因为这就是您的解决方案所做的），那么可能更简洁：

    def unique(lists):
    return list(map(list, set(map(frozenset, lists))))

    如果内部列表可以包含重复项，则上述方法将不起作用，但您可以使用collections.Counter可以充当多重集的列表，然后使用计数器中项目的冻结集：

    from collections import Counter

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

    注意，如果n较小，我相信sorted解决方案会更快。

    • 3

  2. 这是一个图论方法，用于igraph将元组列表转换为无向图

    import igraph as ig
g = ig.Graph.TupleList(lists).simplify()
vnm = g.vs()["name"]
[[vnm[p], vnm[q]] for p, q in g.get_edgelist()]

    由此得出

    [[1, 2], [3, 4]]
    • 0

相关问题