如何判断两个数组是否是彼此的排列（无法对它们进行排序）

Question

如果我有两个不同的数组，而我所能做的就是检查数组中的两个元素是否相等（换句话说，没有比较函数（除了equals）对元素进行排序），是否有任何有效的方法来检查一个数组是否是另一个数组的排列？

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) 表示树集。