比较两个长度相同的整数数组

Question

[描述] 给定两个长度相同的整数数组。设计一种算法来判断它们是否相同。 "相同" 的定义是，如果这两个数组按排序顺序排列，则相应位置上的元素应该相同。

[Example]
<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

[限制] 该算法应该需要恒定的额外空间，并且具有O(n)的运行时间。

- meta

---

已经标记为面试问题。 - Kibbee

嗯...也许是在试图欺骗你，因为明显的方法对于空间复杂度是O(1)，时间复杂度是O(n)...那么问题出在哪里呢？ - mjv

如果您有O(n)的解决方案，请告诉我。 - H H

这个问题完全取决于整数是否有界限...如果整数在两侧都有界限，那么一个计算出现次数的数组将具有恒定的空间需求。如果没有界限，那么这个问题很可能是无解的。 - Antti Huima

有人能解释一下吗，为什么建议对所有元素进行异或并检查0值的答案是不正确的？我想我可能没有看到一些非常明显的东西。 - Amar

Answer 1

（可能对于面试问题来说过于复杂了。）

（您可以使用O（N）时间来检查最小值、最大值、总和、平方和等是否相等。）

使用无额外空间的基数排序原地对两个数组进行排序。时间复杂度为O（N），空间复杂度为O（1）。

然后使用通常的算法进行比较。时间复杂度为O（N），空间复杂度为O（1）。

（提供数组的（最大值-最小值）是O（N^k）且有限的k。）

- kennytm

---

仅当它们是有界整数时才成立。 - Larry

考虑到我们现在讨论的是计算机，它们总是有界的。当然，一个占用了16GB空间的整数会有一个非常大的上限，但它仍然是有界的。 - Jerry Coffin

按照那种逻辑，你可以说幼稚的“哈希表”解决方案是正确的，因为你只需将哈希表设置为一个恒定但巨大的大小即可。 - Larry

@Larry：如果你看一下我的回答，我确实说了那个。 - Jerry Coffin

按照这个逻辑，在有界整数上创建一个大小为MAX_INT的哈希表。这是一个常量，我确定！;P - Larry

Answer 2

你可以尝试一种概率方法——将数组转换为某个巨大进制数B并模以某个质数P，例如对所有i求和B^a_i，然后模以某个较大的P。如果它们得到相同的数字，则可以再尝试多个质数。如果任何尝试都失败，则它们不相等。如果它们通过了足够的挑战，则它们是相等的，有很高的概率。

对于B > N，P >最大数字，有一个显而易见的证明。因此必须存在无法满足的挑战。这实际上是一种确定性方法，尽管复杂度分析可能更加困难，这取决于人们如何看待复杂度与输入大小（而不仅仅是元素数量）的关系。

- Larry

---

总有碰撞的机会。 - Seva Alekseyev

为什么你会说“高概率”，而不是去计算它呢？理论上，无法逾越的最大概率为（1-1/MAX_INT）。 - P Shved

“With high probability” 是概率算法中的一个实际术语，可参考 http://www.algorithmist.com/index.php/With_high_probability。 - Larry

哈哈，我的意思是这是一种写法的速记，尽管这也是Google的第一个结果！ ;) - Larry

似乎所有定义都在论文中。但通常情况下，当你可以将概率尽可能小时，这个术语就被使用了。 - Larry

Answer 3

我认为：除非指定输入范围，否则不可能以恒定的额外空间和O(n)的运行时间解决问题。

如果能证明我是错的，那我会很高兴学到新东西。

- Arun

---

你能证明这个问题的最低限吗？ - meta

我同意，如果没有整数范围，这个问题就无法在O(n)时间和恒定空间内解决。 - faisal

Answer 4

几个答案基本上是正确的，尽管它们看起来不像。例如哈希表方法具有基于涉及类型范围而不是数组中元素数量的上限。至少按照大多数定义，这使得（上限）空间成为一个常量，尽管该常量可能非常大。

理论上，您可以将其从上限更改为真正的恒定空间量。例如，如果您在C或C++中工作，并且它是char数组，则可以使用类似以下内容：

size_t counts[UCHAR_MAX];

由于UCHAR_MAX是一个常量，因此数组使用的空间也是一个常量。

编辑：值得注意的是，在几乎所有算法复杂度的描述中，都隐含着对所涉及项目的范围/大小的限制。例如，我们都“知道”快速排序是O(N log N)算法。然而，这只有在我们假设比较和交换被排序的项需要恒定时间时才成立，这只有在我们限制范围时才可能成立。如果所涉及的项目范围足够大，以至于我们不能再把比较或交换视为需要恒定时间，那么它的复杂度将变成类似于O(N log N log R)的形式，其中R是范围，因此log R近似表示表示一个项目所需的位数。

- Jerry Coffin

---

我不同意你的观点。这样，所有在O(n)时间复杂度下运行的算法都会变成常数时间复杂度，因为如果你有一个大小为n的数组，但你知道n是以整数形式表示的，它的元素数量肯定小于MAX_INT，所以是常数时间复杂度。 - pajton

这就是有时候使得这些面试问题变得学术化的原因。不管怎样，以O(N)为代价并不切实际！ - Larry

@pajton：并不是完全可比较的。你说的是处理数组大小的限制，而我说的是对数组中项的范围的限制，无论其大小如何。 - Jerry Coffin

@Steve：我认为我们在这方面大多数意见一致。我之所以说“几乎全部”是有原因的——虽然可以更加明确，但这只在像教科书和标准等地方比较常见。 - Jerry Coffin

真的，只要人们经常发表荒谬的言论，比如“它不是O(N^2)，而是O(N)”，那么担心他们在第一时间描述什么时，可能没有太多意义；-) - Steve Jessop

Answer 5

1. 将第一个数组的所有元素插入到哈希表中
2. 尝试将第二个数组的所有元素插入到相同的哈希表中，对于每个插入的元素，应该已经存在

好的，这不是使用恒定的额外空间，但这是我目前能想到的最好的方法:-)。在问题上还有其他的限制吗？比如说可能包含在数组中的最大整数？

- pajton

---

将第一个数组中的所有元素插入哈希表中。您需要O(n)内存来分配哈希表，而您只有O(1)的内存可用。 - P Shved

@Pavel：不需要O(n)。如果数组的大小加倍（例如），您期望哈希表的大小也会（大约）加倍，但实际情况并非如此。 - Jerry Coffin

@Pavel，在最坏的情况下我需要O(n)，我在帖子中已经说明了。我知道这只是部分解决方案，但也许可以改进。 - pajton

@Jerry，@pajton，在任何情况下，只要数组中的所有值都不同，您都需要O(n)。当您向表中添加元素时，必须存储您已添加的确切值（以供将来比较）。它将是列表中的新项目（用于桶列表），或者至少需要n个桶（开放地址）。这些都是O(n)。 - P Shved

@pajton，不考虑额外空间成本，你的解决方案仍然是错误的。以以下为例：<1 1 3 3>，<1 3 3 3>你能说它们是相同的吗？ - meta

@meta 没错，但是这里有一个简单的解决方法：使用哈希映射代替哈希表，并使用散列存储每个元素的计数。仍然是 O(n)。 - pajton

Answer 6

这是一个诡计问题吗？如果作者假设整数在给定范围内（2^32等），那么“额外的常量空间”可能只是一个大小为2^32的数组，在其中计算两个列表中的出现次数。

如果整数没有范围，则无法完成。

- Christopher Oezbek

Answer 7

你可以将每个元素添加到一个hashmap 中，并遵循以下规则：数组A是添加器，数组B是删除器。当从数组A插入时，如果键不存在，则插入值为1的键。如果键存在，则增加值（保持计数）。在删除时，如果键存在且大于1，则将其减少1。如果键存在且为1，则删除该元素。

按照上述规则运行数组A，然后是数组B。如果在删除阶段期间数组B没有找到元素，则可以立即返回false。如果添加器和删除器都完成后hashmap为空，则数组相等。

编辑：哈希表的大小将等于数组中不同值的数量，这是否符合常量空间的定义？

- kgrad

---

不，它不等于数组的长度，它等于数组中不同值的数量。 - Svante

Answer 8

我想解决方案需要某种既满足结合律又满足交换律的转换，并保证唯一的输入集有唯一的结果。但是我不确定这是否存在。

- Niki Yoshiuchi

---

我在考虑类似这样的事情，例如证明对于 Z{0,1} 的子集 A、B，其中 |A| = |B|，如果 sum(a_i) = sum(b_i) 且 prod(a_i) = prod(b_i)，那么我们必须在某些排列后得到 A = B ... 困难的部分是证明 :P - Mads Ravn

没错！我尝试使用sum()和prod()，但它失败了-对于几个输入，例如：[-10，-10，-10，-1，9]！= [6，-3，5，-10，-10]，但它们的总和和乘积相等。 - Niki Yoshiuchi

Answer 9

public static boolean match(int[] array1, int[] array2) {

        int x, y = 0;

        for(x = 0; x < array1.length; x++) {
                y = x;
                while(array1[x] != array2[y]) {
                        if (y + 1 == array1.length)
                                return false;
                        y++;
                }
                int swap = array2[x];
                array2[x] = array2[y];
                array2[y] = swap;
        }

        return true;
}

- Edwin Leong

Answer 10

假设整数在范围-n..+n之间，检查它们是否相等的简单方法可能如下所示（伪代码）：

// a & b are the array
accumulator = 0
arraysize = size(a)
for(i=0 ; i < arraysize; ++i) {
  accumulator = accumulator + a[i] - b[i]
  if abs(accumulator) > ((arraysize - i) * n) { return FALSE }
}
return (accumulator == 0)

累加器必须能够存储范围为+-数组大小*n的整数

- Francesco R.