检查一个数组是否是另一个数组的排列版本

Question

我想检查数组 B 是否是数组 A 的排列。

我认为可以使用 1 for -loop 来完成，但是我看到了不同的来源，他们中的大多数人告诉我使用 2 for 循环。

for (int i = 0; i < A.length; i++) {
    boolean found = false;
    for (int j = 0; j < B.length; j++)
        if (B[j] == A[i]) { 
            found = true;
            break; 
        }
        assert(found);
    }
    for (int i = 0; i < B.length; i++) {
        boolean found = false;
        for (int j = 0; j < A.length; j++)
            if (A[j] == B[i]) { 
                found = true; 
                break; 
            }
        assert(found);
    }

这是具有 2 个for循环的正确实现吗？

顺便问一下，为什么我必须执行 2 个for循环，其中第一个循环将 B 与 A 进行比较，然后第二个将 A 与 B 进行比较？

Answer 1

您的代码将排列检查拆分为两个操作：

1. 对于每个元素A[i]检查A[i]是否出现在B
2. 对于每个元素B[j]检查B[j]是否出现在A

正如@Tom所指出的，这在一般情况下不起作用，因为它忽略了重复的元素。

它也是低效的。如果先检查A.length == B.length，则可以省略第二部分，但其余部分仍然O(n²)。它仍然是错误的，因为它在考虑重复元素时返回误报。

或

多或少的规范方法是简单地对两个数组进行排序并比较它们的相等性：

Arrays.sort(A);
Arrays.sort(B);
assert(Arrays.equals(A, B));

排序通常被认为是O(n ln n)的，所以整个操作现在比以前更有效率。它还使事情更具可读性。