发现三胞胎 [英] finding triplets

问题描述

我知道这样的问题之前已经公布，但我想讨论的东西new.So，我张贴。

I know this type of question has been posted before, but i want to discuss something new.So, i am posting it.

由于整数排序的数组，找到满足所有三胞胎X ^ 2 + Y ^ 2 = Z ^ 2。

Given an unsorted array of integers, find all triplets that satisfy x^2 + y^2 = z^2.

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

For example if given array is - 1, 3, 7, 5, 4, 12, 13 The answer should be - 5, 12, 13 and 3, 4, 5

我下面推荐算法中使用复杂度为O（N ^ 2） -

I suggested below algo with complexity O(n^2) -

• 降序排列的数组。 - O（nlogn）
• 在广场的每个元素。 - 为O（n）

现在它减少了寻找所有三胞胎的问题（A，B，C）中的一个排序的数组，使得A = B + C。

Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c.

面试官是坚持一个解决方案为O更好的（N ^ 2）。

The interviewer was insisting on a solution better than O(n^2).

我已经阅读 3SUM的问题，它强调的问题可以在O解决的（N + ulogu），如果号码在范围内的psented作为位向量[-u，U]假设该阵列可以被重新$ P $。但我不能够得到进一步的解释的清晰画面。

I have read 3SUM problem on Wikipedia, which emphasizes problem can be solved in O(n+ulogu) if numbers are in range [-u,u] assuming the array can be represented as a bit vector. But i am not able to get a clear picture of further explanations.

有人可以帮我了解什么是一个很好的例子怎么回事？

Can someone please help me in understanding what is going on with a nice example?

推荐答案

首先。寻找所有三胞胎在最坏的情况下是为O（n ^ 3）。假设你有 N = 3K 的数字。其中K分别3，k为4和k 5

First of all. Finding all triplets in worst case is O(n^3). Suppose you have n=3k numbers. K of them are 3, k are 4 and k are 5.

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

有 K ^ 3 = N ^ 3/27 =为O（n ^ 3）这样的三胞胎。只是打印它们需要为O（n ^ 3）的时间。

There are k^3 = n^3/27 = O(n^3) such triplets. Just printing them takes O(n^3) time.

下一步将解释在这样的形式3SUM问题：

有数字 S_1，...，S_N 的范围内的每个人 [ - U; U] 。有多少三胞胎 A，B，C 有一些 A + B = C ？

There are numbers s_1, ..., s_n each of them in range [-u;u]. How many triplets a,b,c there are that a+b=c?

1. 转化。获得2 *​​ U号 A_-U，...，A_0，A_1，... a_u 。 A_I 为数字量 s_j ，即 s_j = I 。这是在做 O（N + U）

1. transforming. Get 2*u numbers a_-u, ..., a_0, a_1, ... a_u. a_i is amount of numbers s_j, that s_j = i. This is done in O(n+u)

水库= A_0 *总和（I = -u..u，I = / = 0，C（A_I，2））+ C（a_0,3） A_0 = 0

建立一个多项式 P（X）= SUM（I = -u ...ü，A_I * X ^（我+ U）。

查找 Q（X）= P（X）* P（x）使用的 FFT 。

注意 Q（X）= SUM（I = -2u..2u，b_i * X ^（I + 2 * U）），其中 b_i 是对数 S_U ， s_k 的 S_U + s_k = I （这包括使用两次相同的号码）。

Note that Q(x) = sum(i=-2u..2u, b_i*x^(i+2*u)), where b_i is number of pairs s_u,s_k that s_u+s_k = i (This includes using same number twice).

有关所有偶数我 DO b_i = b_i - A_（I / 2）。这将使用两次相同的号码删除。

For all even i do b_i = b_i - a_(i/2). This will remove using same number twice.

示例：更简单，我会假设范围编号为[0..u]并不会在x的权力使用的任何+ U。 假设我们有数字 1,2,3   - A_0 = 0，A_1 = 1，A_2 = 1，A_3 = 1

Example: to be more simple, I will assume that range for numbers is [0..u] and won't use any +u in powers of x. Suppose that we have numbers 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

这篇关于发现三胞胎的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！