p****n
发帖数: 148 | 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*******w
发帖数: 24236 | 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******n
发帖数: 3946 | 3 保证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);
}
} | p****n
发帖数: 148 | 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*****i
发帖数: 122 | 5
【在 p****n 的大作中提到】
: i，j，k元素在数组中的位置吧
: 若是这样无法在有重复元素的情况下保证不出现重复解吧
| i*********7
发帖数: 348 | 6 先sort，然后用vertor存解，然后再将此vector存进set里。set的键值有唯一性，所以
会刷掉重复的 | y**********u
发帖数: 6366 | 7 我觉得set很不decent，有什么办法不用set吗？
【在 i*********7 的大作中提到】
: 先sort，然后用vertor存解，然后再将此vector存进set里。set的键值有唯一性，所以
: 会刷掉重复的
| p****n
发帖数: 148 | 8 “存进set里”的复杂度有多大？算上这个以后的总复杂度是多大？
【在 i*********7 的大作中提到】
: 先sort，然后用vertor存解，然后再将此vector存进set里。set的键值有唯一性，所以
: 会刷掉重复的
|
| S*******w
发帖数: 24236 | 9 我的solution work吗
【在 p****n 的大作中提到】
: i，j，k元素在数组中的位置吧
: 若是这样无法在有重复元素的情况下保证不出现重复解吧
| G******e
发帖数: 229 | 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***y
发帖数: 236 | 11 这样是可以的。先对数组排序，查找就是按顺序的。
【在 S*******w 的大作中提到】
: check当前获得的三元组和前一个
: 如果一样 就不添加到result里面
: 不一样就添加。
:
: a
| y**********u
发帖数: 6366 | 12 相当大
所以应该这么做，其实最小数的循环避开重复的
然后次小数递增的时候在本循环内避开重复的就ok了
所以
【在 p****n 的大作中提到】
: “存进set里”的复杂度有多大？算上这个以后的总复杂度是多大？
| y**********u
发帖数: 6366 | 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**m
发帖数: 535 | 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*********7
发帖数: 348 | 15 其实如果你愿意自己重载hash_map的hash函数和comparator函数的话，倒也是可以不用
set的。
用hash,bool>这个容器类来保证的话，就可以做到o(n^2)。
第一遍用o(n^2)将所有pair存起来，pair的值要顺序存放，这样就不可能会出现重复。
第二遍再用o(n)逐个扫。 | i*********7
发帖数: 348 | 16 另外还有一个空间复杂度没那么高的做法。你记录一下你前一个扫的值。（当然，这需
要在一个排好序的数组里完成）
在外部循环往下扫的时候，如果遇到与你之前刚扫的值相同则跳过。
举个例子。
(-1, -1, -1, 0, 0, 1, 2)
因为你扫了-1，那么记录一下prev = -1。当你扫到下一个-1，你就发现cur = prev.那
你就直接跳过当前的内部循环往下扫到第一个不是-1的数为止，也就是0。 | s********0
发帖数: 34 | 17 思路： 先排序，然后枚举i，取p
void 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++;
}
} |
|
