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++;
}
} |
|