e******s
发帖数: 38 | 1 Two reverse sorted arrays A and B have been given, such that size of A is m
and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B.
看了好多论坛上的答案，好像都不是很清楚。 有一个用max-heap做的，就是每次从
heap里pop出一个
pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。 不知道有没有人有
更清楚的解
法，多谢。 | g*****i
发帖数: 19 | 2 据我所知，用max-heap做的办法（klgn) 是最efficient 办法了。为避免重复，必须用
个变量J-Max track 目前max-heap中所有pair的最大的j. 如果j < J_Max, insert
pair(a[i+1],b[j])到heap里； 如果j = J_Max, 将 pair(a[i],b[j+1]) 和pair(a[i+1
],b[j]) insert到heap里, update as J_Max = J_Max+1.
m
is
里。
【在 e******s 的大作中提到】
: Two reverse sorted arrays A and B have been given, such that size of A is m
: and size of B is n
: You need to find the k th largest sum (a+b) where a is taken from A and b is
: taken from B.
: 看了好多论坛上的答案，好像都不是很清楚。 有一个用max-heap做的，就是每次从
: heap里pop出一个
: pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
: 但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。 不知道有没有人有
: 更清楚的解
: 法，多谢。
| r*******y
发帖数: 1081 | 3 感觉要看k的大小阿，
比如 a1>a2>a3>..., b1>b2>b3>...
那么 kth largest 应该出现在 这 k个 序列里面.
a_i +b_1, a_i + b_2, ..., a_i + b_k
i= 1, 2, ..., k
然后对这 k个序列做 merge sort, 当拿到 第k个数的时候就是 kth largest.
如果k 比较小的话，这个算法还行吧。
m
is
里。
【在 e******s 的大作中提到】
: Two reverse sorted arrays A and B have been given, such that size of A is m
: and size of B is n
: You need to find the k th largest sum (a+b) where a is taken from A and b is
: taken from B.
: 看了好多论坛上的答案，好像都不是很清楚。 有一个用max-heap做的，就是每次从
: heap里pop出一个
: pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
: 但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。 不知道有没有人有
: 更清楚的解
: 法，多谢。
| g**e
发帖数: 6127 | 4 using young tabelau is clearer.
这个特殊的young tableau求前k个最小值以前讨论过，一直没有更好的算法，没有利用
到这个特殊young tableau的属性
求O(n)算法
m
is
里。
【在 e******s 的大作中提到】
: Two reverse sorted arrays A and B have been given, such that size of A is m
: and size of B is n
: You need to find the k th largest sum (a+b) where a is taken from A and b is
: taken from B.
: 看了好多论坛上的答案，好像都不是很清楚。 有一个用max-heap做的，就是每次从
: heap里pop出一个
: pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
: 但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。 不知道有没有人有
: 更清楚的解
: 法，多谢。
| e******s
发帖数: 38 | 5
+1
非常感谢！
【在 g*****i 的大作中提到】
: 据我所知，用max-heap做的办法（klgn) 是最efficient 办法了。为避免重复，必须用
: 个变量J-Max track 目前max-heap中所有pair的最大的j. 如果j < J_Max, insert
: pair(a[i+1],b[j])到heap里； 如果j = J_Max, 将 pair(a[i],b[j+1]) 和pair(a[i+1
: ],b[j]) insert到heap里, update as J_Max = J_Max+1.
:
: m
: is
: 里。
| d****t
发帖数: 6 | 6 Is one single J_Max sufficient?
It needs to be an array J_Maxes instead of one single value J_Max, while
J_Maxes[i] means for each i, the largest J so far. For any given i, the
j_max value is always increasing, but not globally.
pair(a[i+1
【在 g*****i 的大作中提到】
: 据我所知，用max-heap做的办法（klgn) 是最efficient 办法了。为避免重复，必须用
: 个变量J-Max track 目前max-heap中所有pair的最大的j. 如果j < J_Max, insert
: pair(a[i+1],b[j])到heap里； 如果j = J_Max, 将 pair(a[i],b[j+1]) 和pair(a[i+1
: ],b[j]) insert到heap里, update as J_Max = J_Max+1.
:
: m
: is
: 里。
| n********5
发帖数: 323 | 7 reverse sorted arrays 是不是可以 divide and conquer同时比较两个array的值..
. 例如：
a1
b1
可以比较a2<>= b2..
因为找Kth max,同时是reverse sorted. |
|
