arrays - 如何判断两个数组是否是彼此的排列(无法对它们进行排序)

Question

如果我有两个不同的数组，我所能做的就是检查数组中的两个元素是否相等(换句话说，没有比较函数(超越等于)对元素进行排序)，是否有任何有效的检查一个数组是否是另一个数组的排列的方法？

Answer 1

像 Jared 的蛮力解决方案这样的话应该可行，但它是 O(n^2)。

如果元素是可散列的，则可以实现 O(n)。

def isPermutation(A, B):
    """
    Computes if A and B are permutations of each other.
    This implementation correctly handles duplicate elements.
    """
    # make sure the lists are of equal length
    if len(A) != len(B):
        return False

    # keep track of how many times each element occurs.
    counts = {}
    for a in A:
        if a in counts: counts[a] = counts[a] + 1
        else: counts[a] = 1

    # if some element in B occurs too many times, not a permutation
    for b in B:
        if b in counts:
            if counts[b] == 0: return False
            else: counts[b] = counts[b] - 1
        else: return False

    # None of the elements in B were found too many times, and the lists are
    # the same length, they are a permutation
    return True

根据字典的实现方式(作为哈希集与树集)，哈希集的复杂度为 O(n)，树集的复杂度为 O(n log n)。