一FG家常见题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一FG家常见题

一FG家常见题# JobHunting - 待字闺中

p*n2012-04-26 07:04

1 楼

3Sum，原题附在下面
有什么好办法( O(n^2 ) ?)能处理输入中重复的元素，又不产生重复解吗？
如 S = {0, 0, 0, 0, -1, -1, -1, -1, 2},
A solution set is:
(0, 0, 0)
(-1,-1,2)
========
Given an array S of n integers, are there elements a, b, c in S such that a
+ b + c = 0? Find all unique triplets in the array which gives the sum of
zero.
Note:
* Elements in a triplet (a,b,c) must be in non-descending order. (ie, a
≤ b ≤ c)
* The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

S*w2012-04-26 07:04

2 楼

check当前获得的三元组和前一个
如果一样就不添加到result里面
不一样就添加。

a

【在 p****n 的大作中提到】

: 3Sum，原题附在下面
: 有什么好办法( O(n^2 ) ?)能处理输入中重复的元素，又不产生重复解吗？
: 如 S = {0, 0, 0, 0, -1, -1, -1, -1, 2},
: A solution set is:
: (0, 0, 0)
: (-1,-1,2)
: ========
: Given an array S of n integers, are there elements a, b, c in S such that a
: + b + c = 0? Find all unique triplets in the array which gives the sum of
: zero.

s*n2012-04-26 07:04

3 楼

保证ivoid printSum3(int* a, int length, int sum) {
hashtable t = new hashtable();
for (int i=0; it.put(a[i], i);
}
for (int i=0; ifor (int j=i+1; jint k = t.find( sum - a[i] - a[j]);
if (k>j) printf("%d %d %d\n", i, j, k);
}
}

p*n2012-04-26 07:04

4 楼

i，j，k元素在数组中的位置吧
若是这样无法在有重复元素的情况下保证不出现重复解吧

【在 s******n 的大作中提到】

: 保证i: void printSum3(int* a, int length, int sum) {
: hashtable t = new hashtable();
: for (int i=0; i: t.put(a[i], i);
: }
: for (int i=0; i: for (int j=i+1; j: int k = t.find( sum - a[i] - a[j]);
: if (k>j) printf("%d %d %d\n", i, j, k);

d*i2012-04-26 07:04

5 楼

【在 p****n 的大作中提到】

: i，j，k元素在数组中的位置吧
: 若是这样无法在有重复元素的情况下保证不出现重复解吧

i*72012-04-26 07:04

6 楼

先sort，然后用vertor存解，然后再将此vector存进set里。set的键值有唯一性，所以
会刷掉重复的

y*u2012-04-26 07:04

7 楼

我觉得set很不decent，有什么办法不用set吗？

【在 i*********7 的大作中提到】

: 先sort，然后用vertor存解，然后再将此vector存进set里。set的键值有唯一性，所以
: 会刷掉重复的

p*n2012-04-26 07:04

8 楼

“存进set里”的复杂度有多大？算上这个以后的总复杂度是多大？

【在 i*********7 的大作中提到】

: 先sort，然后用vertor存解，然后再将此vector存进set里。set的键值有唯一性，所以
: 会刷掉重复的

S*w2012-04-26 07:04

9 楼

我的solution work吗

【在 p****n 的大作中提到】

: i，j，k元素在数组中的位置吧
: 若是这样无法在有重复元素的情况下保证不出现重复解吧

G*e2012-04-26 07:04

10 楼

You are right, then the complexity would be O(n*nlogn) instead of O(n*n). If
the set is implemented as balanced BST. If unordered_set is used, then only
average case complexity is guaranteed.

【在 p****n 的大作中提到】

: “存进set里”的复杂度有多大？算上这个以后的总复杂度是多大？

q*y2012-04-26 07:04

11 楼

这样是可以的。先对数组排序，查找就是按顺序的。

【在 S*******w 的大作中提到】

: check当前获得的三元组和前一个
: 如果一样就不添加到result里面
: 不一样就添加。
:
: a

y*u2012-04-26 07:04

12 楼

相当大
所以应该这么做，其实最小数的循环避开重复的
然后次小数递增的时候在本循环内避开重复的就ok了

所以

【在 p****n 的大作中提到】

: “存进set里”的复杂度有多大？算上这个以后的总复杂度是多大？

y*u2012-04-26 07:04

13 楼

不行
比如(-1, -1, -1, 0, 0, 1, 2)
从第一个-1开始可以得到
(-1, -1, 2)
(-1, 0, 1)
(-1, 1, 2)
但是从第二个-1开始第二组循环的时候
还会碰到(-1, -1, 2)

that
of

【在 S*******w 的大作中提到】

: check当前获得的三元组和前一个
: 如果一样就不添加到result里面
: 不一样就添加。
:
: a

c*m2012-04-26 07:04

14 楼

第二个循环从0开始就好了，跳过与前一次循环相同的数

【在 y**********u 的大作中提到】

: 不行
: 比如(-1, -1, -1, 0, 0, 1, 2)
: 从第一个-1开始可以得到
: (-1, -1, 2)
: (-1, 0, 1)
: (-1, 1, 2)
: 但是从第二个-1开始第二组循环的时候
: 还会碰到(-1, -1, 2)
:
: that

i*72012-04-26 07:04

15 楼

其实如果你愿意自己重载hash_map的hash函数和comparator函数的话，倒也是可以不用
set的。
用hash,bool>这个容器类来保证的话，就可以做到o(n^2)。
第一遍用o(n^2)将所有pair存起来，pair的值要顺序存放，这样就不可能会出现重复。
第二遍再用o(n)逐个扫。

i*72012-04-26 07:04

16 楼

另外还有一个空间复杂度没那么高的做法。你记录一下你前一个扫的值。（当然，这需
要在一个排好序的数组里完成）
在外部循环往下扫的时候，如果遇到与你之前刚扫的值相同则跳过。
举个例子。
(-1, -1, -1, 0, 0, 1, 2)
因为你扫了-1，那么记录一下prev = -1。当你扫到下一个-1，你就发现cur = prev.那
你就直接跳过当前的内部循环往下扫到第一个不是-1的数为止，也就是0。

s*02012-04-26 07:04

17 楼

思路：先排序，然后枚举i，取pvoid three_sum(int *a, int n, int k){
sort(a, a+n);
for(int i = 0; i < n; i++){
int t = k-a[i];
int p = i+1, q = n-1;
while(p < q){
if(a[p] + a[q] == t){
cout<while(p < q && a[p] == a[p+1]) p++;
p++;// start from next
}
else if(a[p] + a[q] < t) p++;
else q--;
}
while(i+1 < n && a[i] == a[i+1]) i++;
}
}