c*****e
发帖数: 74 | 1 给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A[j
]+A[k]==0.
要求：time complexity in O(n^2),space complexity in O(1).
我只写出了time complexity in O(n^2),space complexity in O(n)；另外程序有几个
小问题。 |
c***2
发帖数: 838 | 2 modification from finding a pair whose sum is equal to a given num |
c*****e
发帖数: 74 | 3 没仔细想过这道题，后面短路了没有把space complexity 降下来。
【在 c***2 的大作中提到】
: modification from finding a pair whose sum is equal to a given num
|
h**********d
发帖数: 4313 | 4 3－sum problem, ihas1337code大侠的blog上有这题 |
d*****t
发帖数: 41 | 5 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
杂度是O(n^2) |
c*****e
发帖数: 74 | 6 我最怕见过又没有认真做过的题，好像有心理障碍，一片麻木。
【在 h**********d 的大作中提到】
: 3－sum problem, ihas1337code大侠的blog上有这题
|
c*****e
发帖数: 74 | 7 当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
我方法，想了半天才明白过来。（心服口服。）
【在 d*****t 的大作中提到】
: 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
: 杂度是O(n^2)
|
D*******i
发帖数: 16 | 8 排序不会改变原来数值的index么？
结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
是我没有理解题意么。。。。
【在 c*****e 的大作中提到】
: 当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
: 我方法，想了半天才明白过来。（心服口服。）
|
c*****e
发帖数: 74 | 9
【在 D*******i 的大作中提到】
: 排序不会改变原来数值的index么？
: 结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
: 如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
: 是我没有理解题意么。。。。
|
c*****e
发帖数: 74 | 10 Only require to return true or false
【在 D*******i 的大作中提到】
: 排序不会改变原来数值的index么？
: 结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
: 如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
: 是我没有理解题意么。。。。
|
|
|
c*****e
发帖数: 74 | 11 给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A[j
]+A[k]==0.
要求：time complexity in O(n^2),space complexity in O(1).
我只写出了time complexity in O(n^2),space complexity in O(n)；另外程序有几个
小问题。 |
c***2
发帖数: 838 | 12 modification from finding a pair whose sum is equal to a given num |
c*****e
发帖数: 74 | 13 没仔细想过这道题，后面短路了没有把space complexity 降下来。
【在 c***2 的大作中提到】
: modification from finding a pair whose sum is equal to a given num
|
h**********d
发帖数: 4313 | 14 3－sum problem, ihas1337code大侠的blog上有这题 |
d*****t
发帖数: 41 | 15 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
杂度是O(n^2) |
c*****e
发帖数: 74 | 16 我最怕见过又没有认真做过的题，好像有心理障碍，一片麻木。
【在 h**********d 的大作中提到】
: 3－sum problem, ihas1337code大侠的blog上有这题
|
c*****e
发帖数: 74 | 17 当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
我方法，想了半天才明白过来。（心服口服。）
【在 d*****t 的大作中提到】
: 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
: 杂度是O(n^2)
|
D*******i
发帖数: 16 | 18 排序不会改变原来数值的index么？
结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
是我没有理解题意么。。。。
【在 c*****e 的大作中提到】
: 当时没有想到在一个排好序的数组里找一个指定和的pair是线性的。后来面试官告诉了
: 我方法，想了半天才明白过来。（心服口服。）
|
c*****e
发帖数: 74 | 19
【在 D*******i 的大作中提到】
: 排序不会改变原来数值的index么？
: 结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
: 如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
: 是我没有理解题意么。。。。
|
c*****e
发帖数: 74 | 20 Only require to return true or false
【在 D*******i 的大作中提到】
: 排序不会改变原来数值的index么？
: 结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
: 如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
: 是我没有理解题意么。。。。
|
|
|
s*******f
发帖数: 1114 | 21 //给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A
[j
//]+A[k]==0.
//要求：time complexity in O(n^2),space complexity in O(1).
//but here the returned index related to the after-sort-array.
//through O(n^2), it still can be improved by using binary search.
//also, if (in[0] + in[1] + in[2] >= sum),
//(in[len-1] + in[len-2] + in[len-3] <= sum) the program need stop.
bool FindThreeNum(int in[], int len, int sum, int out[]){
if (!in || len < 3 || !out)
return false;
std::sort(in, in + len);
for (int i = 0; i < len - 2; ++i){
int j = i + 1;
int k = len - 1;
int two_sum = sum - in[i];
while(j < k){
if (in[j] + in[k] == two_sum){
out[0] = i;
out[1] = j;
out[2] = k;
return true;
}else if(in[j] + in[k] < two_sum){
++j;
}else{
--k;
}
}
}
return false;
} |
z*****n
发帖数: 447 | 22 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)
【在 d*****t 的大作中提到】
: 先排序 O(n*logn)，再先取一个数m，再从剩下的数里找和为-m的两个数，于是时间复
: 杂度是O(n^2)
|
s*******f
发帖数: 1114 | 23 bool FindThreeNum1(int in[], int len, int sum, int out[]){
if (!in || len < 3 || !out)
return false;
std::sort(in, in + len);
int prej = 1;
int prek = len - 1;
for (int i = 0; i < prek - 2; ++i){
bool nobig = true;
bool nosmall = true;
int j = prej;
int k = prek;
int two_sum = sum - in[i];
while(j < k){
if (in[j] + in[k] == two_sum){
out[0] = in[i];
out[1] = in[j];
out[2] = in[k];
return true;
}else if(in[j] + in[k] < two_sum){
nosmall = false;
++j;
if (nobig){
prej = j;
}
}else{
nobig = false;
--k;
if (nosmall){
prek = k;
}
}
}
}
return false;
}
[j
【在 c*****e 的大作中提到】
: 给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A[j
: ]+A[k]==0.
: 要求：time complexity in O(n^2),space complexity in O(1).
: 我只写出了time complexity in O(n^2),space complexity in O(n)；另外程序有几个
: 小问题。
|
b******g
发帖数: 1721 | 24 太有同感了。
而且是觉得是看过了，心里就默认会了，其实自己知道并没有在血液里理解。:-)
【在 c*****e 的大作中提到】
: 我最怕见过又没有认真做过的题，好像有心理障碍，一片麻木。
|
s*****n
发帖数: 994 | 25 bool findZeroSum (int set[], int size){
int i,jk, left, right;
int vi, vj, vk;
bool found=false;
if (size<3) return false;
sort (set,set+size);
for (i=size-1;i>1;i--){
left = 0; right = i-1;
while (right>left){
if (set[left]+set[right]==-set[i]) {found=true; j=left; k=right; break
;}
else if (set[left]+set[right]>-set[i]) left++;
else right--;
}
if (found) break;
}
if (found){
return true;
}return false;
}
+A
【在 s*******f 的大作中提到】
: //给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A
: [j
: //]+A[k]==0.
: //要求：time complexity in O(n^2),space complexity in O(1).
: //but here the returned index related to the after-sort-array.
: //through O(n^2), it still can be improved by using binary search.
: //also, if (in[0] + in[1] + in[2] >= sum),
: //(in[len-1] + in[len-2] + in[len-3] <= sum) the program need stop.
: bool FindThreeNum(int in[], int len, int sum, int out[]){
: if (!in || len < 3 || !out)
|
a********m
发帖数: 15480 | 26 用o(n^2)的排序就好了。
【在 z*****n 的大作中提到】
: 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)
|
y*******g
发帖数: 6599 | 27 heapsort就是inplace nlogn
【在 z*****n 的大作中提到】
: 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)
|
e***s
发帖数: 799 | 28 同问，sort了之后index不是改变了吗？
【在 D*******i 的大作中提到】
: 排序不会改变原来数值的index么？
: 结果要求是返回i,j,k使得a[i]+a[j]+a[k]=0吧?
: 如果空间复杂度为O(1)的话，怎么保存原来的i,j和k啊？
: 是我没有理解题意么。。。。
|
e***s
发帖数: 799 | 29 对不起，我又没认真看回复。。。。
public static bool FindSum(int[] arr)
{
bool found = false;
Array.Sort(arr);
int lenght = arr.Length;
int left, right;
for(int i = lenght - 1; i >= 2; i--)
{
left = 0;
right = i - 1;
while (left < right)
{
if (arr[left] + arr[right] == -arr[i])
return true;
else if (arr[left] + arr[right] < -arr[i])
left++;
else
right--;
}
}
return found;
} |
j********x
发帖数: 2330 | 30 反正这里考虑的重点不是这个部分
【在 z*****n 的大作中提到】
: 时间复杂度 O(n*log(n))的排序算法，空间复杂度都不是O(1)
|
|
|
z******t
发帖数: 59 | 31 There is a detailed solution for this problem on the website:
http://codercareer.blogspot.com/2011/10/no-09-numbers-with-give
[j
【在 c*****e 的大作中提到】
: 给一个数组A[]，写一个程序判断是否能够找到3个不同的index i,j & k 使得A[i]+A[j
: ]+A[k]==0.
: 要求：time complexity in O(n^2),space complexity in O(1).
: 我只写出了time complexity in O(n^2),space complexity in O(n)；另外程序有几个
: 小问题。
|
h*********n
发帖数: 11319 | 32 nice
可以和hash的做法互为补充啊~
+A
几个
【在 z******t 的大作中提到】
: There is a detailed solution for this problem on the website:
: http://codercareer.blogspot.com/2011/10/no-09-numbers-with-give
:
: [j
|
z******t
发帖数: 59 | 33 不然吧。
http://codercareer.blogspot.com/2011/10/no-09-numbers-with-give
中的做法比用hash的算法要好吧。
hash需要O(n)的辅助空间，但链接中的算法不需要
【在 h*********n 的大作中提到】
: nice
: 可以和hash的做法互为补充啊~
:
: +A
: 几个
|
