j**l
发帖数: 2911 | 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. | m*****g
发帖数: 226 | 2 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 | b***u
发帖数: 61 | 3 试试
int a0[] = {5,2,1};
int a1[] = {3,2,1};
MaxPairs(a0,3,a1,3,4);
4个最大和应该是8 7 6 5 而不是8754 | m*****g
发帖数: 226 | 4 果然想简单了
原来根那个样式矩阵一回事
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)的解法 | m*****g
发帖数: 226 | 5 顺便质疑一下goog
这样的问题，是否真的有解，就直接问O(n)的，摆明了耍人么 | b***u
发帖数: 61 | 6 有解的 见careercup那个页面下面Aspirant的方法 | b***u
发帖数: 61 | 7 排序矩阵那个问题比这个强 不能把这个问题reduce到矩阵上 | r****o
发帖数: 1950 | 8 能否给个链接?
【在 b***u 的大作中提到】
: 有解的 见careercup那个页面下面Aspirant的方法
| b***u
发帖数: 61 | 9 照着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)
{
| w*****e
发帖数: 197 | 10 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;
| | | h**6
发帖数: 4160 | | m*****g
发帖数: 226 | 12 这个方法很巧妙阿
有些问题
此处
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;
| x***y
发帖数: 633 | 13 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;
| x***y
发帖数: 633 | 14 Can you give some details about how to use heap on this problem?
【在 h**6 的大作中提到】
: 用堆归并排序效率O(nlgn)，差别不大的。
| l******e
发帖数: 6 | 15 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.....
| x***y
发帖数: 633 | 16 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);
| b***u
发帖数: 61 | 17 你是说n*n的Young table可以在O(n^2)的时间里按顺序输出吗？能详细解释一下吗 谢
谢 | B*****t
发帖数: 335 | 18 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.
| m*****g
发帖数: 226 | 19 请问具体的操作步骤？
【在 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
| r****o
发帖数: 1950 | 20 同问。
【在 m*****g 的大作中提到】
: 请问具体的操作步骤？
| | | B*****t
发帖数: 335 | 21 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; i
hp.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; i
hp.insert(Node(a[ix]+b[p[ix]], ix));
tmp = hp.pop(); | s********a
发帖数: 1447 | 22 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....
| x***y
发帖数: 633 | 23 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."
| x***y
发帖数: 633 | 24 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)的时间里按顺序输出吗？能详细解释一下吗 谢
: 谢
| s********a
发帖数: 1447 | 25 sorry~ 没好好看~ 呵呵
【在 x***y 的大作中提到】
: the 4 is the "4" in a1
| m*****g
发帖数: 226 | 26 请问这题到底是否有解？
高手给个定论？
原题确实比杨矩阵弱。原题有解不能说明杨矩阵也可以。 | a******p
发帖数: 157 | 27 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? |
|
