g******i
发帖数: 354 | 1 我朋友上个星期去的， 纽约， 6 Ave, 450, 纽约的朋友应该都知道这个location的。
(might be headquarter of Morgan Stanley?)
一个数组， say, {8, 10, 2, 9, 5, 7, 1}, 再给另外一个整数，say, 19, 写一个最
快的算法求出19是哪两个元素的和。答案是10, 9. 提示是先Sort， 再用Binary
Search?
可是Sort完后， 怎么用binary Search呀(it'a about the sum, not about 'search')
？ 也许更好的可以用DP (Dynamic Programming)?
我朋友不会， 我也不会。问问版上的牛人， 对这道题， 什么是最好的算法。
Sorry, 忘了说了， 有空间限制， 所以最好不要用Hash. | j***n
发帖数: 301 | 2 sort完了不是binary search吧？可以用2个指针一个从头，一个从尾的找吧
')
【在 g******i 的大作中提到】
: 我朋友上个星期去的， 纽约， 6 Ave, 450, 纽约的朋友应该都知道这个location的。
: (might be headquarter of Morgan Stanley?)
: 一个数组， say, {8, 10, 2, 9, 5, 7, 1}, 再给另外一个整数，say, 19, 写一个最
: 快的算法求出19是哪两个元素的和。答案是10, 9. 提示是先Sort， 再用Binary
: Search?
: 可是Sort完后， 怎么用binary Search呀(it'a about the sum, not about 'search')
: ？ 也许更好的可以用DP (Dynamic Programming)?
: 我朋友不会， 我也不会。问问版上的牛人， 对这道题， 什么是最好的算法。
: Sorry, 忘了说了， 有空间限制， 所以最好不要用Hash.
| k***g
发帖数: 75 | 3 不能用两个指针吧，最快的是用hash
【在 j***n 的大作中提到】
: sort完了不是binary search吧？可以用2个指针一个从头，一个从尾的找吧
:
: ')
| d*******8
发帖数: 785 | 4 不考虑空间最好算法不是Hashtable吗？
')
【在 g******i 的大作中提到】
: 我朋友上个星期去的， 纽约， 6 Ave, 450, 纽约的朋友应该都知道这个location的。
: (might be headquarter of Morgan Stanley?)
: 一个数组， say, {8, 10, 2, 9, 5, 7, 1}, 再给另外一个整数，say, 19, 写一个最
: 快的算法求出19是哪两个元素的和。答案是10, 9. 提示是先Sort， 再用Binary
: Search?
: 可是Sort完后， 怎么用binary Search呀(it'a about the sum, not about 'search')
: ？ 也许更好的可以用DP (Dynamic Programming)?
: 我朋友不会， 我也不会。问问版上的牛人， 对这道题， 什么是最好的算法。
: Sorry, 忘了说了， 有空间限制， 所以最好不要用Hash.
| j***n
发帖数: 301 | 5 嗯，hash不错，免去了sorting，呵呵
【在 k***g 的大作中提到】
: 不能用两个指针吧，最快的是用hash
| h*******u
发帖数: 15326 | 6 sort完了，每个数用19减一下，用binary search找差值，找到就成功 | g**y
发帖数: 122 | | y*****i
发帖数: 727 | 8 先sort，然后维护head tail指针。
如果head+tail>19, set tail point to the middle of the queue, i.e, middle of
[old head, old tail].
if not, head set = middle of the queue.
if equal, return success. | g******e
发帖数: 389 | 9 Binary search is not applicable, at least not as you(above) indicated.
int * find_sum(int *v,int len, int SUM){
quickSort(v,0,len-1);
int low(0), high(len-1);
while(low < high){
if(v[low]+v[high] > SUM) high--; //high = (low+high)/2;
else if(v[low]+v[high] < SUM) low++; //low = (low+high)/2;
else {
int* newV = new int[2];
newV[0] = v[low]; newV[1] = v[high];
return newV;
}
}
return NULL;
} | y**i
发帖数: 1112 | 10 可是sort就需要nlg(n)，sort完了，怎么找也小于nlg(n)吧，那总得最快还是O(nlg(n)
)，怎么也不如hash快啊
【在 h*******u 的大作中提到】
: sort完了，每个数用19减一下，用binary search找差值，找到就成功
| | | b*******y
发帖数: 239 | 11 Sort完然后用19减一下就可以Binary Search了，有人说的Hash具体怎么实现？
Morgan Stanley 在Manhattan有四个办公室，Brooklyn有一个，我在Brooklyn那个做过
Intern， 是911以后都分开这些Office了，让损失降到最低。 | g******i
发帖数: 354 | 12 "Sort完然后用19减一下就可以Binary Search了" 这个好像不行。 你能把程序写出来
吗？
前面的讨论很对，Sort完然后用 Binary Search 应该不行的。 请达人指正。
另外， 我修改了原帖， 原来的题目有空间限制， 用Hash不好。
不过， 如果用Hash的话， 程序如下，关键也是用Hash查找 sum-a[i], 时间复杂度是O(1) if we use Hash to search. 整个程序
complexity is O(n)。
void findSum2() {
int[] a = {8, 10, 2, 9, 5, 7, 1};
int sum = 19;
HashMap hm = new HashMap();
for (int i=0; i
hm.put(a[i], i); //i is the index of the eleme
【在 b*******y 的大作中提到】
: Sort完然后用19减一下就可以Binary Search了，有人说的Hash具体怎么实现？
: Morgan Stanley 在Manhattan有四个办公室，Brooklyn有一个，我在Brooklyn那个做过
: Intern， 是911以后都分开这些Office了，让损失降到最低。
| b*****l
发帖数: 1594 | 13 使用给出的数字（19）作为基数。比如先去找19/2=10 附近的数。然后再找19 -10得到
的数。寻找的时候要换算一个大概的位置。在大数列的时候比较有效。
另一种就是直接找某一个位置，比如数列中间那个，前提是不要超过给出的作为和的整
数。然后再找另一个数。没有就已找到的那个数最近的数找另一个数（或者就是开始认
定的数向前或者向后shift一位，或者在选定数位置1/2处选择，然后循环)。注意防止
重复查找。这个大概和那个IBM的sorting 算法异曲同工。
')
【在 g******i 的大作中提到】
: 我朋友上个星期去的， 纽约， 6 Ave, 450, 纽约的朋友应该都知道这个location的。
: (might be headquarter of Morgan Stanley?)
: 一个数组， say, {8, 10, 2, 9, 5, 7, 1}, 再给另外一个整数，say, 19, 写一个最
: 快的算法求出19是哪两个元素的和。答案是10, 9. 提示是先Sort， 再用Binary
: Search?
: 可是Sort完后， 怎么用binary Search呀(it'a about the sum, not about 'search')
: ？ 也许更好的可以用DP (Dynamic Programming)?
: 我朋友不会， 我也不会。问问版上的牛人， 对这道题， 什么是最好的算法。
: Sorry, 忘了说了， 有空间限制， 所以最好不要用Hash.
| x******3
发帖数: 245 | 14 A = {8, 10, 2, 9, 5, 7, 1}
sum = 19
sort A first
sort_A = {1, 2 ,5, 7, 8, 9, 10}
把1从sort_A中拿出， 19-1=18
在 {2, 5, 7, 8, 9, 10} 中binary search 18，
没找到的话， 把2从{2,5,7,8,9,10}中拿出， 19-2=17,
在{5,7,8,9,10}找17
以此类推
是O(1) if we use Hash to search.
整个程序
【在 g******i 的大作中提到】
: "Sort完然后用19减一下就可以Binary Search了" 这个好像不行。 你能把程序写出来
: 吗？
: 前面的讨论很对，Sort完然后用 Binary Search 应该不行的。 请达人指正。
: 另外， 我修改了原帖， 原来的题目有空间限制， 用Hash不好。
: 不过， 如果用Hash的话， 程序如下，关键也是用Hash查找 sum-a[i], 时间复杂度是O(1) if we use Hash to search. 整个程序
: complexity is O(n)。
: void findSum2() {
: int[] a = {8, 10, 2, 9, 5, 7, 1};
: int sum = 19;
:
| g******i
发帖数: 354 | 15 多谢。简洁明了。
不过这样找的话， 要用nlog(n) (loop the array is n, and binary search is log(
n)).
In additon to that, the first step: sorting is nlong(n) as well.
plus this two steps together = 2nlog(n), and it's still nlong(n) in
complexity.
【在 x******3 的大作中提到】
: A = {8, 10, 2, 9, 5, 7, 1}
: sum = 19
: sort A first
: sort_A = {1, 2 ,5, 7, 8, 9, 10}
: 把1从sort_A中拿出， 19-1=18
: 在 {2, 5, 7, 8, 9, 10} 中binary search 18，
: 没找到的话， 把2从{2,5,7,8,9,10}中拿出， 19-2=17,
: 在{5,7,8,9,10}找17
: 以此类推
:
| h********e
发帖数: 1972 | 16 我来贴个答案吧。。动态规划不怎么可取，因为多半是伪多项式的。hashtable 也不好
，怎么说呢，hash都是投机取巧。很多面试摆明了不要你hash的答案。sort吧，挺好。
。重点是然后可以这么做。。
8, 10, 2, 9, 5, 7, 1
排好序是
1 2 5 7 8 9 10
然后用19 减一下是
18 17 14 12 11 10 9
然后干啥。。
用一次merge排序的merge方法。。就能用n的时间找到是否两个序列有相同的东西了。
当然还有些细节。。
这样好歹能拿出个nlog+2n的算法。。还凑合，当然如果考官只要求O(nlogn)就无所谓
了。 | x**y
发帖数: 10012 | 17 负数呢？
【在 h********e 的大作中提到】
: 我来贴个答案吧。。动态规划不怎么可取，因为多半是伪多项式的。hashtable 也不好
: ，怎么说呢，hash都是投机取巧。很多面试摆明了不要你hash的答案。sort吧，挺好。
: 。重点是然后可以这么做。。
: 8, 10, 2, 9, 5, 7, 1
: 排好序是
: 1 2 5 7 8 9 10
: 然后用19 减一下是
: 18 17 14 12 11 10 9
: 然后干啥。。
: 用一次merge排序的merge方法。。就能用n的时间找到是否两个序列有相同的东西了。
| i**********b
发帖数: 77 | 18 这个找不到
如果一个数在前半部呢？
of
【在 y*****i 的大作中提到】
: 先sort，然后维护head tail指针。
: 如果head+tail>19, set tail point to the middle of the queue, i.e, middle of
: [old head, old tail].
: if not, head set = middle of the queue.
: if equal, return success.
| h**m
发帖数: 187 | 19 提示的那个算法应该就是这个吧
【在 b*****l 的大作中提到】
: 使用给出的数字（19）作为基数。比如先去找19/2=10 附近的数。然后再找19 -10得到
: 的数。寻找的时候要换算一个大概的位置。在大数列的时候比较有效。
: 另一种就是直接找某一个位置，比如数列中间那个，前提是不要超过给出的作为和的整
: 数。然后再找另一个数。没有就已找到的那个数最近的数找另一个数（或者就是开始认
: 定的数向前或者向后shift一位，或者在选定数位置1/2处选择，然后循环)。注意防止
: 重复查找。这个大概和那个IBM的sorting 算法异曲同工。
:
: ')
| q*********u
发帖数: 280 | 20 感觉这种办法比较清爽也好懂
用基本相同的代码， 还可以用来做给出一个数组，比如{1, 2, 1, -1, -4, 10, 2, 9,
8, -6, 1}, 然后找出subarray which has a max summation among other subarrays;
Binary search is not applicable, at least not as you(above) indicated.
int * find_sum(int *v,int len, int SUM){
quickSort(v,0,len-1);
int low(0), high(len-1);
while(low < high){
if(v[low]+v[high] > SUM) high--; //high = (low+high)/2;
else if(v[low]+v[high] < SUM) low++; //low = (low+high)/2;
else {
int* newV =
【在 g******e 的大作中提到】
: Binary search is not applicable, at least not as you(above) indicated.
: int * find_sum(int *v,int len, int SUM){
: quickSort(v,0,len-1);
: int low(0), high(len-1);
: while(low < high){
: if(v[low]+v[high] > SUM) high--; //high = (low+high)/2;
: else if(v[low]+v[high] < SUM) low++; //low = (low+high)/2;
: else {
: int* newV = new int[2];
: newV[0] = v[low]; newV[1] = v[high];
| l**********g
发帖数: 426 | 21 int get_two(int *nlist, int sum, int *n1, int *n2)
{
quicksort(nlist);
left = 0;
right = len(nlist) - 1;
while(right > left)
{
while(left < right && nlist[left]+nlist[right]
{
++left;
}
if (nlist[left]+nlist[right]==sum)
{
*n1 = nlist[left];
*n2 = nlist[right];
return 0
}
--right;
}
return 1;
}
change a little then u can find all pairs |
|
