15

考虑以下问题：

给定一个未排序的整数数组，找出所有满足 x^2 + y^2 = z^2 的三元组。

例如，如果给定数组是1, 3, 7, 5, 4, 12, 13，则答案应该是5, 12, 13and3, 4, 5

我建议使用复杂度为 O(n^2) 的以下算法：

  • 对数组进行降序排序，O(nlogn)
  • 对每个元素求平方，O(n)

现在它简化为在一个有序数组中找到所有三元组（a，b，c）的问题，使得 a = b+c。

面试官坚持要一个比 O(n^2) 更好的解决方案。

我在 Wikipedia 上阅读了 3SUM 问题，它强调如果数字在 [-u,u] 范围内，则问题可以在 O(n+ulogu) 中解决，假设数组可以表示为位向量。但我无法清楚地了解进一步的解释。

有人可以帮助我理解一个很好的例子发生了什么吗？

4

2 回答 2

7

首先。在最坏的情况下找到所有三元组是O(n^3). 假设你有n=3k数字。其中 K 为 3，k 为 4，k 为 5。

3,....,3,4,....,4,5,.....5

有k^3 = n^3/27 = O(n^3)这样的三胞胎。只是打印它们需要O(n^3)时间。

接下来将以这种形式解释 3SUM 问题：

它们每个都有数字s_1, ..., s_nrange [-u;u]。a,b,c那有多少个三胞胎a+b=c？

  1. 转变。获取 2*u 个数字a_-u, ..., a_0, a_1, ... a_u。a_i是数字的数量s_j，那s_j = i。这是在O(n+u)

  2. res = a_0 * sum(i=-u..u, i=/=0, C(a_i, 2)) + C(a_0,3) a_0 = 0

  3. 建立一个多项式P(x) = sum(i = -u...u, a_i*x^(i+u)。

  4. Q(x) = P(x)*P(x)使用FFT查找。

  5. 请注意Q(x) = sum(i=-2u..2u, b_i*x^(i+2*u))，其中b_i是对数s_u，s_k即s_u+s_k = i（这包括两次使用相同的数字）。

  6. 对于所有甚至i做b_i = b_i - a_(i/2)。这将使用相同的号码删除两次。

  7. 总和b_i*a_i/2- 将其添加到 res 中。

示例：为了更简单，我将假设数字的范围是 [0..u]，并且不会使用任何 x 次方的 +u。假设我们有数字1,2,3 -a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 1

  • res = 0

  • P(x) = x + x^2 + x^3

  • Q(x) = x^2 +2x^3+3x^4+2x^5+x^6

  • 减去后b_2 = 0, b_3 = 2, b_4 = 2, b_5 = 2, b_6 = 0

  • res += 0*1/2 + 2*1/2 + 2*0/2 + 2*0/2 + 6*0/2 = 1

于 2012-06-11T10:42:11.340 回答
7

另一种可能性（谁能理解面试官的想法？）将等式重写为：

 x^2 + y^2 = z^2
 x^2 = z^2 - y^2 = (z-y)(z+y)

如果我们知道 x^2 的素数分解，那么我们可以简单地将所有可能的因式分解成一对数字 p,q（p < q）并计算

 x^2 = p.q = (z-y)(z+y)
 p+q = (z-y)+(z+y) = 2z
 q-p = (z+y)-(z-y) = 2y
 z = (p+q)/2
 y = (q-p)/2

所以给定一个因式分解 x^2=pq 我们可以计算出 z 和 y 值。通过将所有整数值放入一个集合中，我们可以在 O(1) 时间内检查每个可能的答案（每次检查），通过查看这些 z,y 值是否在数组中（注意也检测到负值） .

维基百科说一个随机选择的整数大约有 log(n) 除数，所以这应该需要大约 n.log(n) 假设你可以足够快地进行因式分解（例如，如果你知道所有整数都低于一百万，你可以预先计算一个数组每个整数的最小因子）。

于 2012-06-12T20:02:25.977 回答