D***h
发帖数: 183 | 1 给定一个integer array, a1,a2...an,
找出所有a,b,c,d使得a+b = c+d.
很容易找到O(n^2)空间，O(n^2)时间的算法，不知道有没有更快更好的。 | g**f
发帖数: 414 | 2 如果没有任何限制，应该不能，比如
a1＝a2＝...＝an。
【在 D***h 的大作中提到】
: 给定一个integer array, a1,a2...an,
: 找出所有a,b,c,d使得a+b = c+d.
: 很容易找到O(n^2)空间，O(n^2)时间的算法，不知道有没有更快更好的。
| D***h
发帖数: 183 | 3 假定,a1, a2, ...,an没有重复吧。
【在 g**f 的大作中提到】
: 如果没有任何限制，应该不能，比如
: a1＝a2＝...＝an。
| g***s
发帖数: 3811 | 4 then O(n^3).
e.g. 1,2,3....n
the output is O(n^3)
algo is easy for O(n^3)
【在 D***h 的大作中提到】
: 假定,a1, a2, ...,an没有重复吧。
| D***h
发帖数: 183 | 5 如果换一下,a,b,c,d 是1，2，。。。，n中的整数，
求出所有满足a^3+b^3=c^3+d^3的pairs，不知道会不会不一样。
【在 g***s 的大作中提到】
: then O(n^3).
: e.g. 1,2,3....n
: the output is O(n^3)
: algo is easy for O(n^3)
| g**e
发帖数: 6127 | 6 如果要输出(a,b)=(c,d)这样的pair，怎么也要O(n^3)
如果只是要输出所有和相等的pair的集合，类似 {(a,b), (c,d)}, {(e,f), (g,h), (i
,j)} 这样的，O(n^2)倒是容易
【在 g***s 的大作中提到】
: then O(n^3).
: e.g. 1,2,3....n
: the output is O(n^3)
: algo is easy for O(n^3)
|
|
