c*********n
发帖数: 1057 | 1 How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
B
e.g.
A={10,8,5,3,2}
B={11,9,5,3}
Find 4th Largest pair gives: 9 + 8 = 17
Any nice solutions? | c*b
发帖数: 3126 | 2 类似merge sort的最后一步？
and
【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?
| c*********n
发帖数: 1057 | 3 然后呢？你意思吧A and B 合并？
然后怎么找出 Nth largest pair啊？
【在 c*b 的大作中提到】
: 类似merge sort的最后一步？
:
: and
| c*b
发帖数: 3126 | 4 弄个数组按降序记录pair的和
前N个都能找出来吧
【在 c*********n 的大作中提到】
: 然后呢？你意思吧A and B 合并？
: 然后怎么找出 Nth largest pair啊？
| c*********n
发帖数: 1057 | 5 那还是O(n^2)啊
【在 c*b 的大作中提到】
: 弄个数组按降序记录pair的和
: 前N个都能找出来吧
| h**k
发帖数: 3368 | 6 naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
和，然后merge 找nth个，复杂度是O(n*n)
更好的方法是O(nlogn)
这个和是一个partial order，(x,y)表示A[x]+B[y]，则
(0,0) > (0,1) > (0,2) >...
> > >
(1,0) > (1,1) > (1,2) >...
> > >
(2,0) > (2,1) > (2,2) >...
>
...
从(0,0)开始，把(0,0)存入heap of size n,
输出heap中的最大值，然后把(0,1)和（1，0）放入heap，再输出最大值。
suppose the maximum element in the heap is (i,j)，remove it and insert( i+1,
j) and (i,j+1) into the heap. Count the output number.
有个问题，(i,j)可能会被放入heap
【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?
| c*********n
发帖数: 1057 | 7 就是按照反对角线的顺序把元素放到heap是吧，恩好方法
但是细节好象还要考虑下，到底怎么输出Nth max，因为比如 4th的话
（2，0） （1，1） （0，2）都有可能的
所以我觉得O(N)应该就可以了吧？
因为找到相应的反对角线的第几行，然后比较那一行中的几个元素就可以了啊
但是给第一个N*N的Matrix，输入k,怎么得到是第几排呢？
比如k=4，是第3排，k=7 or 8 or 9 or 10是第4排
【在 h**k 的大作中提到】
: naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
: 和，然后merge 找nth个，复杂度是O(n*n)
: 更好的方法是O(nlogn)
: 这个和是一个partial order，(x,y)表示A[x]+B[y]，则
: (0,0) > (0,1) > (0,2) >...
: > > >
: (1,0) > (1,1) > (1,2) >...
: > > >
: (2,0) > (2,1) > (2,2) >...
: >
| c*********n
发帖数: 1057 | 8
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~想了一下，用个for就可以，所以谢谢你的提示，我觉
得O(N)就可以找到了，如果有什么不对请指正
【在 c*********n 的大作中提到】
: 就是按照反对角线的顺序把元素放到heap是吧，恩好方法
: 但是细节好象还要考虑下，到底怎么输出Nth max，因为比如 4th的话
: （2，0） （1，1） （0，2）都有可能的
: 所以我觉得O(N)应该就可以了吧？
: 因为找到相应的反对角线的第几行，然后比较那一行中的几个元素就可以了啊
: 但是给第一个N*N的Matrix，输入k,怎么得到是第几排呢？
: 比如k=4，是第3排，k=7 or 8 or 9 or 10是第4排
| h**k
发帖数: 3368 | 9
其实，这里(0,1)和(1,0)都有可能。比如
10，9，8，1
10，6，2，1
前第4个就是(0,0),(1,0),(2,0),(0,1)
【在 c*********n 的大作中提到】
: 就是按照反对角线的顺序把元素放到heap是吧，恩好方法
: 但是细节好象还要考虑下，到底怎么输出Nth max，因为比如 4th的话
: （2，0） （1，1） （0，2）都有可能的
: 所以我觉得O(N)应该就可以了吧？
: 因为找到相应的反对角线的第几行，然后比较那一行中的几个元素就可以了啊
: 但是给第一个N*N的Matrix，输入k,怎么得到是第几排呢？
: 比如k=4，是第3排，k=7 or 8 or 9 or 10是第4排
| s*********t
发帖数: 1663 | 10 和最小的n个pair，必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
这个不对吧？ | | | c*********n
发帖数: 1057 | 11 我也觉得这个存在严重bug
比如
A={10,8,1}
B={10,9,1}
4th 应该是8+9
【在 s*********t 的大作中提到】
: 和最小的n个pair，必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
: 这个不对吧？
| c*********n
发帖数: 1057 | 12 你能不能详细解释下这个heap的用法？
到底需要存多少个元素进heap？并且是哪些元素？
如何解决一下的问题的：
A={10,9,8,7}
B={10,2,1,0}
找4th max，应该是10+7
【在 h**k 的大作中提到】
: naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
: 和，然后merge 找nth个，复杂度是O(n*n)
: 更好的方法是O(nlogn)
: 这个和是一个partial order，(x,y)表示A[x]+B[y]，则
: (0,0) > (0,1) > (0,2) >...
: > > >
: (1,0) > (1,1) > (1,2) >...
: > > >
: (2,0) > (2,1) > (2,2) >...
: >
| b******v
发帖数: 1493 | 13 假设Ai+Bj在和最小的n个pair里面，但是i和j都不等于0
那么我们把它换成A0+Bj或者Ai+B0，都能得到更小的数
所以在考虑完那2n个数之前，不必考虑i,j都不等于0的情形
【在 s*********t 的大作中提到】
: 和最小的n个pair，必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
: 这个不对吧？
| c*********n
发帖数: 1057 | 14 看不懂，举个反例吧：
A 1,2,10,100
B 1,3,20,200
最小的4个数为什么不包括 2+3呢？
【在 b******v 的大作中提到】
: 假设Ai+Bj在和最小的n个pair里面，但是i和j都不等于0
: 那么我们把它换成A0+Bj或者Ai+B0，都能得到更小的数
: 所以在考虑完那2n个数之前，不必考虑i,j都不等于0的情形
| g**********1
发帖数: 1113 | 15 how can you know A1+B1 is greater than A0+B4?
【在 b******v 的大作中提到】
: 假设Ai+Bj在和最小的n个pair里面，但是i和j都不等于0
: 那么我们把它换成A0+Bj或者Ai+B0，都能得到更小的数
: 所以在考虑完那2n个数之前，不必考虑i,j都不等于0的情形
| g**********1
发帖数: 1113 | 16 Normally you have n*n matrix with columns and rows are sorted. You can merge
all columns at nlogn complexity. | c*********n
发帖数: 1057 | 17
`~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~我
之前的回复已经给反例了，你在看看？
【在 b******v 的大作中提到】
: 假设Ai+Bj在和最小的n个pair里面，但是i和j都不等于0
: 那么我们把它换成A0+Bj或者Ai+B0，都能得到更小的数
: 所以在考虑完那2n个数之前，不必考虑i,j都不等于0的情形
| g**********1
发帖数: 1113 | 18 Normally you have n*n matrix with columns and rows are sorted. You can merge
all columns at nlogn complexity. | b******v
发帖数: 1493 | 19 有道理，我错了
【在 c*********n 的大作中提到】
: 看不懂，举个反例吧：
: A 1,2,10,100
: B 1,3,20,200
: 最小的4个数为什么不包括 2+3呢？
| g**********1
发帖数: 1113 | 20 how about this case?
size of A =4 and size of B =4
but the smallest 4 is: 1+1, 1+2,2+1 and 2+3 but 2+3 is not A0+Bi or Ai+B0
right?
【在 c*********n 的大作中提到】
: 看不懂，举个反例吧：
: A 1,2,10,100
: B 1,3,20,200
: 最小的4个数为什么不包括 2+3呢？
| | | c*********n
发帖数: 1057 | 21
merge
~~~~~~~~~~~~~Can you show the algorithm?
【在 g**********1 的大作中提到】
: Normally you have n*n matrix with columns and rows are sorted. You can merge
: all columns at nlogn complexity.
| y****n
发帖数: 579 | 22 你的假设在n小于Nth的N时成立。
【在 s*********t 的大作中提到】
: 和最小的n个pair，必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
: 这个不对吧？
| X*********n
发帖数: 570 | 23 assume A has n elements and B has m, and n<=m
then we can have n lists
a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
.....
a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
then we build a max-heap with the first element of each list with O(n).
delete the max from the heap and insert the next element from the
corresponding list, O(logn)
do it N times
So the complexity is O(Nlogn)
and
【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?
| c*********n
发帖数: 1057 | 24 恩，这个感觉是对的thanks
【在 X*********n 的大作中提到】
: assume A has n elements and B has m, and n<=m
: then we can have n lists
: a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
: a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
: .....
: a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
: then we build a max-heap with the first element of each list with O(n).
: delete the max from the heap and insert the next element from the
: corresponding list, O(logn)
: do it N times
| h**6
发帖数: 4160 | 25 其实，对于多于两个数组的元素和或积排序，也可以用这个堆的办法。 | u**s
发帖数: 50 | 26 This method looks like O(nlogn).
However, when you code it, you will notice that dedup is a little bit
annoying.
If you create a bitmap/boolean for n^2 and init to false, then this is
already n^2. Of course, you can use other hashtable to solve this, but just
looks ugly.
If you ignore this issue, then you can say this is O(nlogn) ...
【在 h**k 的大作中提到】
: naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
: 和，然后merge 找nth个，复杂度是O(n*n)
: 更好的方法是O(nlogn)
: 这个和是一个partial order，(x,y)表示A[x]+B[y]，则
: (0,0) > (0,1) > (0,2) >...
: > > >
: (1,0) > (1,1) > (1,2) >...
: > > >
: (2,0) > (2,1) > (2,2) >...
: >
| b*******7
发帖数: 907 | 27 The time complexity of building a n-element heap should be O(nlogn) because
inserting element needs O(logn). | X*********n
发帖数: 570 | 28 heap building can be done in linear time, please check CLRS 6.3
because
【在 b*******7 的大作中提到】
: The time complexity of building a n-element heap should be O(nlogn) because
: inserting element needs O(logn).
| h**6
发帖数: 4160 | 29 这个容易，用STL中的set就可以解决。
定义一个priority_queue, vector >, greater
> >
再定义一个set >
每次在set里面检查，如果没有就加入priority_queue，同时加入set。当从堆顶移除时
，也从set中删除。
just
【在 u**s 的大作中提到】
: This method looks like O(nlogn).
: However, when you code it, you will notice that dedup is a little bit
: annoying.
: If you create a bitmap/boolean for n^2 and init to false, then this is
: already n^2. Of course, you can use other hashtable to solve this, but just
: looks ugly.
: If you ignore this issue, then you can say this is O(nlogn) ...
| h**k
发帖数: 3368 | 30 你一共放入堆的数总数是n*n，最后是O(n*n*log)
【在 X*********n 的大作中提到】
: assume A has n elements and B has m, and n<=m
: then we can have n lists
: a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
: a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
: .....
: a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
: then we build a max-heap with the first element of each list with O(n).
: delete the max from the heap and insert the next element from the
: corresponding list, O(logn)
: do it N times
| | | h**k
发帖数: 3368 | 31
heap本身大小不固定，就是一个max-heap，第一个放入的元素是10+10,
pop, 然后放入10+9，10+2，pop 10+9,放入10+8，然后pop 10+8，放入10+7
【在 c*********n 的大作中提到】
: 你能不能详细解释下这个heap的用法？
: 到底需要存多少个元素进heap？并且是哪些元素？
: 如何解决一下的问题的：
: A={10,9,8,7}
: B={10,2,1,0}
: 找4th max，应该是10+7
| h**k
发帖数: 3368 | 32 set本身是靠bst来实现的，每个查询/删除/插入都是O(logn)，所以最好的数据结构这
里就是hash_table
pair
【在 h**6 的大作中提到】
: 这个容易，用STL中的set就可以解决。
: 定义一个priority_queue, vector >, greater: > >
: 再定义一个set >
: 每次在set里面检查，如果没有就加入priority_queue，同时加入set。当从堆顶移除时
: ，也从set中删除。
:
: just
| b******v
发帖数: 1493 | 33 又没有说要把所有的pair排序，只要找出前N个就行了，所以是O(N*log(n))
【在 h**k 的大作中提到】
: 你一共放入堆的数总数是n*n，最后是O(n*n*log)
| c***p
发帖数: 221 | 34 (a[i], b[j]) 构成了young tableau.所以这个问题就是找young tableau第K大的元素.
and
【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?
| h**k
发帖数: 3368 | 35 嗯，我搞错了。
【在 b******v 的大作中提到】
: 又没有说要把所有的pair排序，只要找出前N个就行了，所以是O(N*log(n))
| h**k
发帖数: 3368 | 36 嗯，我搞错了。
【在 b******v 的大作中提到】
: 又没有说要把所有的pair排序，只要找出前N个就行了，所以是O(N*log(n))
| h**6
发帖数: 4160 | 37 假设两个数组，各有1000000项
a[]={1000000, 999999, 999998, ..., 2, 1}
b[]={2000000, 1999999, 1999998, ..., 1000002, 1000001}
求第1000000大的ai+bj是多少，可以编程试试，看几秒钟能够出来。 | h**6
发帖数: 4160 | 38 写了个程序，执行时间半秒到一秒之间，结果是2998002，大家可以试一试。
#include
#include
#include
using namespace std;
const int N = 1000000;
const int M = 1000000;
inline void InsertHeapSet(int* a, int i, int* b, int j, priority_queue
int, pair > >& Q, set >& S)
{
Q.push(pair >(a[i]+b[j], pair(i, j)));
S.insert(pair(i, j));
}
void main()
{
int* a = new int [N];
int* b = new int [N];
for(int i=0; i
{
【在 h**6 的大作中提到】
: 假设两个数组，各有1000000项
: a[]={1000000, 999999, 999998, ..., 2, 1}
: b[]={2000000, 1999999, 1999998, ..., 1000002, 1000001}
: 求第1000000大的ai+bj是多少，可以编程试试，看几秒钟能够出来。
| c******n
发帖数: 4965 | 39 did u pass ur algo course ?
【在 X*********n 的大作中提到】
: heap building can be done in linear time, please check CLRS 6.3
:
: because
| l*****a
发帖数: 559 | 40 i think what he means is building a heap for a sorted array will cost
constant time.
【在 c******n 的大作中提到】
: did u pass ur algo course ?
|
|
