algorithm - 检查数组 B 是否是 A 的排列

Question

我试图找到解决这个问题的办法，但想不出太多办法。

我们有两个未排序的整数数组 A 和 B。我们必须检查数组 B 是否是 A 的排列。这如何完成。？即使对数字进行异或运算也无法正常工作，因为可能有多个具有相同异或值的反例 bt 不是彼此的排列。

解决方案需要 O(n) 时间和空间 O(1)

欢迎任何帮助!!谢谢。

Answer 1

这个问题是理论上的，但你可以在 O(n) 时间和 o(1) 空间内完成。分配一个包含 2³² 个计数器的数组，并将它们全部设置为零。这是 O(1) 步骤，因为数组的大小不变。然后遍历这两个数组。对于数组 A，增加与读取的整数对应的计数器。对于数组 B，将它们递减。如果在数组 B 的迭代过程中遇到负计数器值，请停止 --- 数组不是彼此的排列。否则在最后(假设 A 和 B 具有相同的大小，先决条件)计数器数组全为零并且两个数组是彼此的排列。

这是 O(1) 空间和 O(n) 时间的解决方案。然而，它不实用，但很容易作为面试问题的解决方案通过。至少应该如此。

更晦涩的解决方案

• 使用非确定性计算模型，检查两个数组是否不是彼此的排列可以在 O(1) 空间内完成，O( n) 通过猜测在两个数组中具有不同计数的元素计时，然后计算该元素在两个数组中的实例数。

• 在随机计算模型中，构造一个随机交换哈希函数并计算两个数组的哈希值。如果散列值不同，则数组不是彼此的排列。否则他们可能会。重复多次以使错误概率低于所需阈值。同样在 O(1) 空间 O(n) 时间方法上，但是是随机的。

• 在并行 计算模型中，设“n”为输入数组的大小。分配'n'个线程。每个线程 i = 1 .. n 从第一个数组中读取第 i 个数；让它成为x。然后同一个线程计算 x 在第一个数组中出现的次数，然后在第二个数组中检查相同的计数。每个线程使用 O(1) 空间和 O(n) 时间。

• 将整数数组 [ a1, ..., an ] 解释为多项式 x^a1 + x^a2 + ... + x^an 其中 x 是一个自由变量，并在数值上检查所获得的两个多项式的等价性。使用浮点算法进行 O(1) 空间和 O(n) 时间操作。由于舍入误差和数值检查等价性是概率性的，因此不是精确的方法。或者，解释以素数为模的整数多项式，并执行相同的概率检查。