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?
相关阅读
睾丸较小的男性是“更好”的父亲？ (转载)东岸有哪些测转录组的公司？美国最近30年占尽了中国的便宜 (转载)问个问题：生物材料方向怎么样？求教文章署名有没有什么挥发快的但又不伤酶的溶剂求怎样选择中秋前夕，投稿被接受，发120个中秋月饼关于shRNA retroviral screen的一个问题请问生物PHD办 EB1 难吗？学生物的能去那些医药公司？清洁用品里的灭菌剂和过敏的发生有关系回报本版，biotech找工经验给老千们指一条明路大家投稿都会严格按照journal的格式吗万能干细胞anyone try lentiviral particles from santa cruz?HMS的CME有用吗？method paper老板想一拆为二发，求意见调查
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。