logo
Redian新闻
>未名空间
>Biology - 生物学
>
paper help and thanks with BAOZI
avatar
paper help and thanks with BAOZI# Biology - 生物学
j*l
1 楼
http://www.careercup.com/question?id=2007663
Given two sorted postive integer arrays A(n) and B(n) (let's say they are
decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}.
Obviously there are n^2 elements in S. The value of such a pair is defined
as Val(a,b) = a + b. Now we want to get the n pairs from S with largest
values. Need an O(n) algorithm.
avatar
m*g
3 楼
void MaxPairs(int *array1, int lenArray1, int *array2, int lenArray2, int
numPairs)
{
int end1, end2, cnt;
end1=end2=1; //end of the elements that are used.
cnt=2; //how many elements we have gathered
if(numPairs > (lenArray1*lenArray2)) return;

/*take care of when lenArray1 or lenArray2 is 1*/

while(cnt{
if(array1[end1]>array2[end2]) end1++;
else end2++;
cnt = end1*end2;
}
printf("%d %d\n", end1, end2);
int
avatar
b*u
5 楼
试试
int a0[] = {5,2,1};
int a1[] = {3,2,1};
MaxPairs(a0,3,a1,3,4);
4个最大和应该是8 7 6 5 而不是8754
avatar
m*g
7 楼
果然想简单了
原来根那个样式矩阵一回事
let a={a0>a1>a2...>an}
b={b0>b1>b2...>bm}
s={bm+an bm+an-1 ... bm+an;
...
...
b0+an b0+an-1 ... b0+a0;}
求最大的n个。
用样式矩阵那样一个一个找的话得n2
同求O(n)的解法
avatar
m*g
9 楼
顺便质疑一下goog
这样的问题，是否真的有解，就直接问O(n)的，摆明了耍人么
avatar
b*u
10 楼
有解的 见careercup那个页面下面Aspirant的方法
avatar
b*u
11 楼
排序矩阵那个问题比这个强 不能把这个问题reduce到矩阵上
avatar
r*o
12 楼
能否给个链接?

【在 b***u 的大作中提到】
: 有解的 见careercup那个页面下面Aspirant的方法
avatar
b*u
13 楼
照着Aspirant的方法编的
public static void printSum(int[] a,int[] b, int n)
{
int xi,yi,xj,yj;
if(n>a.length * b.length)
n = a.length * b.length;
xi=0;
yi=1;
xj=1;
yj=0;
System.out.printf("(%d,%d) ",a[0],b[0]);
while(n>0)
{
if(a[xi]+b[yi] > a[xj]+b[yj])
{
System.out.printf("(%d,%d) ",a[xi],b[yi]);
yi++;
if(yi == b.length)
{
avatar
w*e
14 楼
I don't see how this could work.

【在 b***u 的大作中提到】
: 照着Aspirant的方法编的
: public static void printSum(int[] a,int[] b, int n)
: {
: int xi,yi,xj,yj;
: if(n>a.length * b.length)
: n = a.length * b.length;
: xi=0;
: yi=1;
: xj=1;
: yj=0;
avatar
h*6
15 楼
用堆归并排序效率O(nlgn)，差别不大的。
avatar
m*g
16 楼
这个方法很巧妙阿
有些问题
此处
System.out.printf("(%d,%d) ",a[xj],b[yj]);
xj++;
为何xj和b.length有关，难道不是a.length么
if(xj == b.length)
{
yj++;
xj = Math.max(xi+1,yj+1);

【在 b***u 的大作中提到】
: 照着Aspirant的方法编的
: public static void printSum(int[] a,int[] b, int n)
: {
: int xi,yi,xj,yj;
: if(n>a.length * b.length)
: n = a.length * b.length;
: xi=0;
: yi=1;
: xj=1;
: yj=0;
avatar
x*y
17 楼
This is not correct....It fails in the situation when (x1, y1) is the 4th
largest pair...That Aspirant guy gave his idea after the code, note that the
next possible candidate can be more than 2 pairs.....
Actually, if this can be done in linear time, then finding the min n in a n*
n Y table can be done in linear too, which is impossbile.....

【在 b***u 的大作中提到】
: 照着Aspirant的方法编的
: public static void printSum(int[] a,int[] b, int n)
: {
: int xi,yi,xj,yj;
: if(n>a.length * b.length)
: n = a.length * b.length;
: xi=0;
: yi=1;
: xj=1;
: yj=0;
avatar
x*y
18 楼
Can you give some details about how to use heap on this problem?

【在 h**6 的大作中提到】
: 用堆归并排序效率O(nlgn)，差别不大的。
avatar
l*e
19 楼
int a1[] = {5,2,1};
int a2[] = {3,2,1};
用4个指针指向两个数组（头和尾分别是（5，2）和（3，2）），同时扫描连个数组并
比较大小，每
次只挪动一个尾指针；直到一个数组结束，再修改头指针。
void output(int* a1, int* a2, int* b, int n)
{
int count = 1;
b[0] = a1[0]+a2[0];
int i1(0), i2(0), j1(1), j2(1);
while (count < n)
{
if (a1[i1]+a2[j2] > a2[i2]+a1[j1])
{
b[count] = a1[i1]+a2[j2];
j2++;
if (j2 == n)
{
j2 = 1;
i1++;
}
}
else


【在 x***y 的大作中提到】
: This is not correct....It fails in the situation when (x1, y1) is the 4th
: largest pair...That Aspirant guy gave his idea after the code, note that the
: next possible candidate can be more than 2 pairs.....
: Actually, if this can be done in linear time, then finding the min n in a n*
: n Y table can be done in linear too, which is impossbile.....
avatar
x*y
20 楼
I know what the method is about, but it's not correct.
Say a1[]={5, 4, 1} a2[]={4, 3, 1} Then the result would be
5+4 = 9
5+3 = 8
4+4 = 8
4+3 = 7 //but in your method is either is 5+1 or 4+1
I have said that the problem with the approach is that there may be more
than 2 candidates for next pair.......
I know with Young talbe, we can get a O(n^2) solution...But how to get
better, like O(nlogn) is very difficult for me....

【在 l******e 的大作中提到】
: int a1[] = {5,2,1};
: int a2[] = {3,2,1};
: 用4个指针指向两个数组（头和尾分别是（5，2）和（3，2）），同时扫描连个数组并
: 比较大小，每
: 次只挪动一个尾指针；直到一个数组结束，再修改头指针。
: void output(int* a1, int* a2, int* b, int n)
: {
: int count = 1;
: b[0] = a1[0]+a2[0];
: int i1(0), i2(0), j1(1), j2(1);
avatar
b*u
21 楼
你是说n*n的Young table可以在O(n^2)的时间里按顺序输出吗？能详细解释一下吗 谢
谢
avatar
B*t
22 楼
This can be solved in time O(nlogn) + extra space O(n) by creating
a max-heap, but I don't think there is an O(n) solution.

they are
\in B}.
is defined
largest

【在 j**l 的大作中提到】
: http://www.careercup.com/question?id=2007663
: Given two sorted postive integer arrays A(n) and B(n) (let's say they are
: decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}.
: Obviously there are n^2 elements in S. The value of such a pair is defined
: as Val(a,b) = a + b. Now we want to get the n pairs from S with largest
: values. Need an O(n) algorithm.
avatar
m*g
23 楼
请问具体的操作步骤？

【在 B*****t 的大作中提到】
: This can be solved in time O(nlogn) + extra space O(n) by creating
: a max-heap, but I don't think there is an O(n) solution.
:
: they are
: \in B}.
: is defined
: largest
avatar
r*o
24 楼
同问。

【在 m*****g 的大作中提到】
: 请问具体的操作步骤？
avatar
B*t
25 楼
code
struct Node {
int val, ix;
bool operator>(const Node &ot) {
return val>ot.val;
}
Node(int _v=0, int _ix=0):val(_v), ix(_ix){}
};
int a[N]={...}, b[N]={...}
int i, j, p[N] = {0}, res[N]={0};;
MaxHeap hp;
for(i=0; ihp.insert(Node(a[i]+b[0], i));
}

Node tmp = hp.pop();
p[tmp.ix]++;
res[0] = tmp.val;
int ix = tmp.ix;
for(i=1; ihp.insert(Node(a[ix]+b[p[ix]], ix));
tmp = hp.pop();
avatar
s*a
26 楼
en?
4 and 3 are both in a2[].
but
"we define a set S = {(a,b) | a \in A and b \in B}.
The value of such a pair is defined
as Val(a,b) = a + b."

【在 x***y 的大作中提到】
: I know what the method is about, but it's not correct.
: Say a1[]={5, 4, 1} a2[]={4, 3, 1} Then the result would be
: 5+4 = 9
: 5+3 = 8
: 4+4 = 8
: 4+3 = 7 //but in your method is either is 5+1 or 4+1
: I have said that the problem with the approach is that there may be more
: than 2 candidates for next pair.......
: I know with Young talbe, we can get a O(n^2) solution...But how to get
: better, like O(nlogn) is very difficult for me....
avatar
x*y
27 楼
the 4 is the "4" in a1

【在 s********a 的大作中提到】
: en?
: 4 and 3 are both in a2[].
: but
: "we define a set S = {(a,b) | a \in A and b \in B}.
: The value of such a pair is defined
: as Val(a,b) = a + b."
avatar
x*y
28 楼
I mean you can output n min elements of n*n Young table in order in O(n^2), not
all the elements in the table....

【在 b***u 的大作中提到】
: 你是说n*n的Young table可以在O(n^2)的时间里按顺序输出吗？能详细解释一下吗 谢
: 谢
avatar
s*a
29 楼
sorry~ 没好好看~ 呵呵

【在 x***y 的大作中提到】
: the 4 is the "4" in a1
avatar
m*g
30 楼
请问这题到底是否有解？
高手给个定论？
原题确实比杨矩阵弱。原题有解不能说明杨矩阵也可以。
avatar
a*p
31 楼
One condition in this problem makes the problem much easier, but all of the
aforementioned methods seem not to utilize it.
If the values of pairs are calculated by a*b, then it becomes hard.
The array sizes are n, and we only need to get n maximum pairs.
All the pairs can only be (a0,bx) or (ax,bx). Then the problem can be solved
in O(n), right?
相关阅读
关于opt麻烦问一下订做抗体的话哪个公司比较好,费用大概是多说?问个职业选择问题，转行做技术支持有前途吗？申请博后该怎么写career goal?其实人类历史上从来没有未来战士也就说明了未来永远没有时间机器求junctional proteins （ZO-1, V-Cadherin, etc）抗体～谢谢～没有心思看买卖题了YFP真核转染后能在普通倒置荧光显微镜下看吗？Mammalian 的 CMV promoter能在果蝇S2细胞里表达吗刚生的小老鼠怎么注射tamoxifen？Paper help讨论：生物口海归回国前景堪忧 (转载)请问Princeton的Carlos Brody怎么样？热情已然耗尽请教关于hyperbolic curve的线性范围医科大学基础部饶毅施一公落选院士疑因回国时间短非中国籍zz包子求好用的Kit或WB信息-测小鼠外周血IGF-I的求一篇论文，先谢啦dose-response curve 求解读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。