10

我试图找到解决方案，但无法摆脱我的想法。

给定两个未排序的整数数组 A 和 B。我们必须检查数组 B 是否是 A 的置换。如何做到这一点。即使对数字进行异或也不起作用，因为可能有几个反例具有相同的异或值 bt 不是彼此的排列。

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

欢迎任何帮助！谢谢。

4

9 回答 9

11

这个问题是理论上的，但你可以在 O(n) 时间和 o(1) 空间内完成。分配一个由 2 32 个计数器组成的数组并将它们全部设置为零。这是 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) 时间操作使用浮点运算。由于舍入误差和等价的数值检查是概率性的，这不是一种精确的方法。或者，解释以素数为模的整数多项式，并执行相同的概率检查。

于 2012-05-17T16:52:50.273 回答
7

如果我们被允许自由访问大量素数，您可以通过利用素数分解的特性来解决这个问题。

对于这两个数组，计算每个整数 i 的 Prime[i] 的乘积，其中 Prime[i] 是第 i 个素数。如果它们是彼此的排列，则数组乘积的值相等。

质因数分解在这里有帮助有两个原因。

  1. 乘法是传递的，因此计算乘积的操作数的顺序是无关紧要的。（有些人提到如果对数组进行排序，这个问题将是微不足道的。通过乘法，我们隐式排序。）
  2. 素数无损相乘。如果给定一个数字，并告诉它它只是素数的乘积，我们可以准确计算出输入了哪些素数以及具体有多少。

例子：

a = 1,1,3,4
b = 4,1,3,1
Product of ith primes in a = 2 * 2 * 5 * 7 = 140
Product of ith primes in b = 7 * 2 * 5 * 2 = 140

也就是说，我们可能不允许访问素数列表，但这似乎是一个很好的解决方案，所以我想我会发布它。

于 2012-05-20T04:08:31.060 回答
5

我很抱歉将其发布为答案，因为它确实应该是对 antti.huima 答案的评论，但我还没有评论的声誉。

计数器数组的大小似乎是 O(log(n))，因为它取决于输入数组中给定值的实例数。

例如，让输入数组 A 全为 1，长度为 (2^32) + 1。这将需要一个大小为 33 位的计数器进行编码（实际上，这会使数组的大小加倍，但让我们坚持理论）。将 A 的大小加倍（仍然是所有 1 值），每个计数器需要 65 位，依此类推。

这是一个非常挑剔的论点，但这些面试问题往往非常挑剔。

于 2012-05-18T15:50:47.117 回答
3

如果我们不需要就地排序，那么以下方法可能会起作用：

  1. 创建一个 HashMap，Key 作为数组元素，Value 作为出现次数。（处理相同数字的多次出现）
  2. 遍历数组 A。
  3. 在 HashMap 中插入数组元素。
  4. 接下来，遍历数组 B。
  5. 在 HashMap 中搜索 B 的每个元素。如果对应的值为 1，则删除该条目。否则，将值减 1。
  6. 如果我们能够处理整个数组 B 并且此时 HashMap 为空，则成功。否则失败。

HashMap 将使用常量空间，您将只遍历每个数组一次。

不确定这是否是您正在寻找的。如果我错过了关于空间/时间的任何限制，请告诉我。

于 2012-05-20T22:39:22.800 回答
1

解决方案需要 O(n) 时间和 O(1) 空间。这省略了排序，并且空间 O(1) 要求暗示您可能应该对字符串进行散列并进行比较。

如果您可以访问素数列表，请按照 Checheen 的解决方案进行操作。

注意：如果面试官说您无权访问质数列表。然后生成质数并存储它们。这是 O(1)，因为字母长度是一个常数。

否则，这是我的替代想法。为简单起见，我将 Alphabet 定义为 = {a,b,c,d,e}。字母的值定义为：

a, b, c, d, e
1, 2, 4, 8, 16

注意：如果面试官说这是不允许的，那么为 Alphabet 做一个查找表，这需要 O(1) 空间，因为 Alphabet 的大小是一个常数

定义一个可以在字符串中找到不同字母的函数。

// set bit value of char c in variable i and return result
distinct(char c, int i) : int

E.g. distinct('a', 0) returns 1
E.g. distinct('a', 1) returns 1
E.g. distinct('b', 1) returns 3

因此，如果您迭代字符串“aab”，则 distinct 函数应给出 3 作为结果

定义一个可以计算字符串中字母总和的函数。

// return sum of c and i
sum(char c, int i) : int

E.g. sum('a', 0) returns 1
E.g. sum('a', 1) returns 2
E.g. sum('b', 2) returns 4

因此，如果您迭代字符串“aab”，sum 函数应该给出 4 作为结果

定义一个可以计算字符串中字母长度的函数。

// return length of string s
length(string s) : int

E.g. length("aab") returns 3

在两个字符串上运行方法并比较结果需要 O(n) 运行时间。存储散列值需要 O(1) 的空间。

 e.g. 
 distinct of "aab" => 3
 distinct of "aba" => 3
 sum of "aab => 4
 sum of "aba => 4
 length of "aab => 3
 length of "aba => 3

由于两个字符串的所有值都相等，因此它们必须是彼此的排列。

编辑：解决方案与评论中指出的给定字母值不正确。

于 2012-05-28T14:32:05.130 回答
1

您有两个约束：计算 O(n)，其中 n 表示 A 和 B 的总长度以及内存 O(1)。

如果两个系列A，B是彼此的排列，那么还有一个系列C是由A或B的排列产生的。所以问题是将A和B都排列成系列C_A和C_B并比较它们。

一种这样的排列是排序。有几种排序算法可以就地工作，因此您可以就地对 A 和 B 进行排序。现在，在最佳情况下，平滑排序使用 O(n) 计算和 O(1) 内存复杂度进行排序，在最坏情况下使用 O(n log n) / O(1)。

然后每个元素的比较发生在 O(n)，但由于在 O 表示法 O(2*n) = O(n) 中，使用平滑排序和比较会给你一个 O(n) / O(1) 检查是否两个系列是彼此的排列。然而，在最坏的情况下，它将是 O(n log n)/O(1)

于 2012-05-20T22:53:28.010 回答
0

我只是找到一个反例。所以，下面的假设是不正确的。

我无法证明这一点，但我认为这可能是真的。

由于数组的所有元素都是整数，假设每个数组有 2 个元素，我们有

a1 + a2 = s
a1 * a2 = m

b1 + b2 = s
b1 * b2 = m

then {a1, a2} == {b1, b2}

如果这是真的，那么对于具有 n 个元素的数组来说也是如此。

所以我们比较每个数组的和和乘积，如果相等，一个是另一个的排列。

于 2012-05-18T16:01:50.380 回答
0

You can convert one of the two arrays into an in-place hashtable. This will not be exactly O(N), but it will come close, in non-pathological cases.

Just use [number % N] as it's desired index or in the chain that starts there. If any element has to be replaced, it can be placed at the index where the offending element started. Rinse , wash, repeat.

UPDATE: This is a similar (N=M) hash table It did use chaining, but it could be downgraded to open addressing.

于 2012-05-17T16:53:09.110 回答
0

我会使用一个错误几率很低的随机算法。

关键是使用通用散列函数。

def hash(array, hash_fn):
  cur = 0
  for item in array:
    cur ^= hash_item(item)
  return cur

def are_perm(a1, a2):
  hash_fn = pick_random_universal_hash_func()
  return hash_fn(a1, hash_fn) == hash_fn(a2, hash_fn)

如果数组是排列，它总是正确的。如果它们不同，算法可能会错误地认为它们是相同的，但这样做的概率非常低。此外，通过在同一输入上询问许多 are_perm() 问题，您可以通过线性工作量获得错误机会的指数减少，如果它曾经说不，那么它们绝对不是彼此的排列。

于 2012-05-17T18:20:24.450 回答