2

给定两个大小为 N 的整数数组，设计一种算法来确定一个是否是另一个的排列。也就是说，它们是否包含完全相同的条目，但可能以不同的顺序。

我可以想到两种方法：对它们进行排序并比较：O(N.log N + N)

检查数组是否有相同数量的整数并且这些整数的和是否相同，然后对两个数组进行异或，看看结果是否为 0。这是 O(N)。我不确定这种方法是否会完全消除误报。想法。更好的算法？

4

4 回答 4

3

检查数组是否有相同数量的整数并且这些整数的和是否相同，然后对两个数组进行异或，看看结果是否为 0。

这行不通。例子：

a = [1,6]  length(a) = 2, sum(a) = 7, xor(a) = 7
b = [3,4]  length(b) = 2, sum(b) = 7, xor(b) = 7

其他人已经建议HashMap使用 O(n) 解决方案。

这是使用 C# 的 O(n) 解决方案Dictionary<T, int>：

bool IsPermutation<T>(IList<T> values1, IList<T> values2)
{
    if (values1.Count != values2.Count)
    {
        return false;
    }

    Dictionary<T, int> counts = new Dictionary<T, int>();
    foreach (T t in values1)
    {
        int count;
        counts.TryGetValue(t, out count);
        counts[t] = count + 1;
    }

    foreach (T t in values2)
    {
        int count;
        if (!counts.TryGetValue(t, out count) || count == 0)
        {
            return false;
        }
        counts[t] = count - 1;
    }

    return true;
}

在 Python 中，您可以使用Counter该类：

>>> a = [1, 4, 9, 4, 6]
>>> b = [4, 6, 1, 4, 9]
>>> c = [4, 1, 9, 1, 6]
>>> d = [1, 4, 6, 9, 4]
>>> from collections import Counter
>>> Counter(a) == Counter(b)
True
>>> Counter(c) == Counter(d)
False
于 2012-08-20T22:05:56.793 回答
2

如果空间复杂度O(n)不是问题，您可以O(n)通过首先将第一个数组中每个值的出现次数存储在哈希映射中，然后在第二个数组上运行第二遍并检查每个元素存在于地图中，减少每个元素的出现次数。

于 2012-08-20T22:11:30.640 回答
2

最好的解决方案可能是使用其键是两个数组中的值的映射进行计数。

通过一个数组创建/增加适当的地图位置，并通过另一个数组创建/减少适当的地图位置。

如果生成的映射完全由零组成，则您的数组是相等的。

这是 O(N)，我认为你不能做得更好。

我怀疑这大概就是 Mark Byers 在他的回答中想要的。

于 2012-08-20T22:17:22.753 回答
0

对两个数组的内容进行数字排序，然后比较每个第 n 项。

您还可以获取 array1 中的每个项目，然后检查它是否存在于 array2 中。数一数你找到了多少匹配项。最后，匹配的数量应该等于数组的长度。

于 2012-08-20T22:08:49.817 回答