如何高效地比较两个未排序的列表（而不是集合）？

29 浏览
0 Comments

如何高效地比较两个未排序的列表（而不是集合）？

a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]

应该认为 a & b 是相等的，因为它们拥有完全相同的元素，只是顺序不同。

问题在于，我的实际列表将由对象（我的类实例）而不是整数组成。

admin 更改状态以发布 2023年5月23日
0

2 答案

0 Comments

你可以对两个进行排序：

sorted(a) == sorted(b)

计数排序也可以更加有效（但需要对象是可哈希的）。

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True

0
0 Comments

O(n): Counter() 方法是最好的选择（如果你的对象是可哈希的）:

def compare(s, t):
    return Counter(s) == Counter(t)

O(n log n): 接下来最好的选择是 sorted() 方法（如果你的对象是可序的）:

def compare(s, t):
    return sorted(s) == sorted(t)

O(n * n): 如果对象既不可哈希也不可序，你可以使用相等性:

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

0