A*********r
发帖数: 564 | 1 you are given 2 arrays sorted in decreasing order of size m and n
respectively.
Input: a number k <= n*m and >= 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
如果直接一个一个算的话，从大到小，需要O(k)复杂度。
不知道最优解是多少，是O(logk) 还是O(1) ?
在careercup上看到的，有人提出来了最优解是O(1), 但是觉得不太对头。。 | r***u
发帖数: 241 | 2 直接算O(k)怎么算？
【在 A*********r 的大作中提到】
: you are given 2 arrays sorted in decreasing order of size m and n
: respectively.
: Input: a number k <= n*m and >= 1
: Output: the kth largest sum(a+b) possible. where
: a (any element from array 1)
: b (any element from array 2)
: 如果直接一个一个算的话，从大到小，需要O(k)复杂度。
: 不知道最优解是多少，是O(logk) 还是O(1) ?
: 在careercup上看到的，有人提出来了最优解是O(1), 但是觉得不太对头。。
| h**k
发帖数: 3368 | 3 O(k)的算法极其复杂，发表过一篇论文。比较简单的是O(klogk)的复杂度。
【在 A*********r 的大作中提到】
: you are given 2 arrays sorted in decreasing order of size m and n
: respectively.
: Input: a number k <= n*m and >= 1
: Output: the kth largest sum(a+b) possible. where
: a (any element from array 1)
: b (any element from array 2)
: 如果直接一个一个算的话，从大到小，需要O(k)复杂度。
: 不知道最优解是多少，是O(logk) 还是O(1) ?
: 在careercup上看到的，有人提出来了最优解是O(1), 但是觉得不太对头。。
| b*****n
发帖数: 221 | 4 O(KlogK)是用的heap吧?
这个题的变形是一个数组,找最小/大的K个pairs.
【在 h**k 的大作中提到】
: O(k)的算法极其复杂，发表过一篇论文。比较简单的是O(klogk)的复杂度。
| b********r
发帖数: 118 | 5 应该是O(k)
两个sorted数组 a和b
a[0]+b[0]一定是最大的 a[0]+b[1] and a[1]+b[0]谁第二大不一定 比一下 然后挪a或者b的index
不过比较麻烦 code没写出来... | l**o
发帖数: 356 | 6 有可能a[0]+a[1]的呀
或者b的index
【在 b********r 的大作中提到】
: 应该是O(k)
: 两个sorted数组 a和b
: a[0]+b[0]一定是最大的 a[0]+b[1] and a[1]+b[0]谁第二大不一定 比一下 然后挪a或者b的index
: 不过比较麻烦 code没写出来...
| b********r
发帖数: 118 | 7 用java写的 应该没问题了 需要四个指针
public class SumTest {
public static void main( String[] args ){
int[] a = {9, 7, 2};
int[] b = {6, 3, 1};
int k = 3;
int i = 0;
int i_1 = 1;
int j = 0;
int j_1 = 1;
int m = 1;
int current_sum=a[0]+b[0];
while(i
if(a[i]+b[i_1] > a[j_1]+b[j]){
if ( current_sum != a[i]+b[i_1]){
current_sum = a[i]+b[i_1];
| b********r
发帖数: 118 | 8 不可能 条件
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
【在 l**o 的大作中提到】
: 有可能a[0]+a[1]的呀
:
: 或者b的index
| A*********r
发帖数: 564 | 9 能简单说一下四个指针的意义么？
【在 b********r 的大作中提到】
: 用java写的 应该没问题了 需要四个指针
: public class SumTest {
: public static void main( String[] args ){
: int[] a = {9, 7, 2};
: int[] b = {6, 3, 1};
: int k = 3;
: int i = 0;
: int i_1 = 1;
: int j = 0;
: int j_1 = 1;
| A*********r
发帖数: 564 | 10 那个check current_sum与当前值是否相等，好像不太正确，毕竟可能出现当前sum和下
一个sum相同的情况的啊。。
【在 b********r 的大作中提到】
: 用java写的 应该没问题了 需要四个指针
: public class SumTest {
: public static void main( String[] args ){
: int[] a = {9, 7, 2};
: int[] b = {6, 3, 1};
: int k = 3;
: int i = 0;
: int i_1 = 1;
: int j = 0;
: int j_1 = 1;
| | | A*********r
发帖数: 564 | 11 这个算法是错的，四个指针其中两个是主指针，分别track数组a和b的位置，另外两个
可以看作是副指针，分别遍历与主指针相对应的另外一个数组中的位置。
比如说，数组a的主指针移动，只有在其对应的副指针在b已经到达尾部的时候。这个逻
辑是不对的，因为有可能（2，2）的sum比其他的 （1， X） 或者 (Y,1)都大（这里都
是index pairs)
比如：a= { 9, 8, 5, 4}
b={ 7, 6, 3}
这个算法的输出为 (9,7) --(9,6) --(8,7)--(7,5)--
注意(8,6)被跳过去了，明显比(7,5)大。。
【在 b********r 的大作中提到】
: 用java写的 应该没问题了 需要四个指针
: public class SumTest {
: public static void main( String[] args ){
: int[] a = {9, 7, 2};
: int[] b = {6, 3, 1};
: int k = 3;
: int i = 0;
: int i_1 = 1;
: int j = 0;
: int j_1 = 1;
| A*********r
发帖数: 564 | 12 我找了好久，没有找到正确的O(k)的算法。。
如果用max heap,把后两个可能最大sum都放进去,估计能达到O（klogk),不过用c写起来
也不简单的样子..
【在 h**k 的大作中提到】
: O(k)的算法极其复杂，发表过一篇论文。比较简单的是O(klogk)的复杂度。
| r***u
发帖数: 241 | 13
能不能解释一下klogk的算法
【在 A*********r 的大作中提到】
: 我找了好久，没有找到正确的O(k)的算法。。
: 如果用max heap,把后两个可能最大sum都放进去,估计能达到O（klogk),不过用c写起来
: 也不简单的样子..
| b********r
发帖数: 118 | 14 是不对 再想想啊
【在 A*********r 的大作中提到】
: 这个算法是错的，四个指针其中两个是主指针，分别track数组a和b的位置，另外两个
: 可以看作是副指针，分别遍历与主指针相对应的另外一个数组中的位置。
: 比如说，数组a的主指针移动，只有在其对应的副指针在b已经到达尾部的时候。这个逻
: 辑是不对的，因为有可能（2，2）的sum比其他的 （1， X） 或者 (Y,1)都大（这里都
: 是index pairs)
: 比如：a= { 9, 8, 5, 4}
: b={ 7, 6, 3}
: 这个算法的输出为 (9,7) --(9,6) --(8,7)--(7,5)--
: 注意(8,6)被跳过去了，明显比(7,5)大。。
| b********r
发帖数: 118 | 15 对啊 为什么不是(n+m)lg(n+m)呢
【在 r***u 的大作中提到】
:
: 能不能解释一下klogk的算法
| x******3
发帖数: 245 | 16 klogk的是不是这样
build (m*n-k)-min-heap
还剩下k个元素， 逐个和heap的top比较，如果比top大，就把top置换成新元素，从新
heapify
最后heap top就是kth largest
【在 b********r 的大作中提到】
: 对啊 为什么不是(n+m)lg(n+m)呢
| b********r
发帖数: 118 | 17 你是说build (m+n-k)-min-heap?
这样 worst case k=1 还是(n+m)lg(n+m)啊
【在 x******3 的大作中提到】
: klogk的是不是这样
: build (m*n-k)-min-heap
: 还剩下k个元素， 逐个和heap的top比较，如果比top大，就把top置换成新元素，从新
: heapify
: 最后heap top就是kth largest
| r**u
发帖数: 1567 | 18 build (m*n-k)-min-heap --> complexity is O(m*n)
【在 x******3 的大作中提到】
: klogk的是不是这样
: build (m*n-k)-min-heap
: 还剩下k个元素， 逐个和heap的top比较，如果比top大，就把top置换成新元素，从新
: heapify
: 最后heap top就是kth largest
| x******3
发帖数: 245 | 19 是的
k = O(m*n)
【在 r**u 的大作中提到】
: build (m*n-k)-min-heap --> complexity is O(m*n)
| x******3
发帖数: 245 | | | | w*****p
发帖数: 215 | 21 greedy。
举个例子，
A ： 10 9 5 3 1
B ： 8 7 5 3 k 为 5
首先， 最大的肯定是 10+8=18
然后把A,B换成差额数组， 就是 A[i]-A[i+1]
数组变成 1 4 2 2 和 1,1,1,2
从这里开始， 选取两个数组中最小的数，并且把另个数组的当前数减去 这个小的数。
并且把当前和（初始为18）减去这个小数。这个步骤重复到K次就行了。
比如这个例子，第二小的从A里面出，和变成18-1， B的当前数是 1-1=0， 然后A 向后
移，即指向4。 第三小的从B里出，和变成 17 - 0， A的当前数是 4 - 0= 4， B 向后
移到 1.
同理，最后第5小的数是15， 是 9 + 6.
有空来写code，今天心烦。 | w*****p
发帖数: 215 | 22 从这里开始， 选取两个数组中当前（指针从头开始）最小的数(就比较 a[i] 和 b[j],
i 和 j 是当前指针，index or whatever)，并且把另个数组的当前数减去 这个小的
数。
并且把当前和（初始为18）减去这个小数。这个步骤重复到K次就行了。 | e*********r
发帖数: 546 | 23 ding
这个觉得挺对的，楼下的不同意么？
或者b的index
【在 b********r 的大作中提到】
: 应该是O(k)
: 两个sorted数组 a和b
: a[0]+b[0]一定是最大的 a[0]+b[1] and a[1]+b[0]谁第二大不一定 比一下 然后挪a或者b的index
: 不过比较麻烦 code没写出来...
| e******a
发帖数: 176 | 24 我感觉这个不对啊。A和B里每一个element 都要有一个指针，这个指针指向相对于该
element自身来
说，在对面数组里的当前位置。所以这个brute force 的复杂度是1+2+3+...+k = O(k
^2). 如
果用min heap, 是 log1+log2+...+logk =k(logk)
【在 w*****p 的大作中提到】
: greedy。
: 举个例子，
: A ： 10 9 5 3 1
: B ： 8 7 5 3 k 为 5
: 首先， 最大的肯定是 10+8=18
: 然后把A,B换成差额数组， 就是 A[i]-A[i+1]
: 数组变成 1 4 2 2 和 1,1,1,2
: 从这里开始， 选取两个数组中最小的数，并且把另个数组的当前数减去 这个小的数。
: 并且把当前和（初始为18）减去这个小数。这个步骤重复到K次就行了。
: 比如这个例子，第二小的从A里面出，和变成18-1， B的当前数是 1-1=0， 然后A 向后
| i*********l
发帖数: 766 | 25 整个算法有点像minimum spanning tree，
z=x+y是个二维函数。我们从原点开始。有把确定的结果涂黑。第一个涂黑的是（1，1）
下一个涂黑的只能是（1，2）或者（2，1），我们只要比较这两个就可以了。假设是（
1，2）比较大，那就是（1，2）涂黑。。那下一个candidate只可能在（1，3），（2，
1）或者（2，2)，candidate有什么特点呢。就是涂黑的那些点的横坐标或者总坐标加1
。而且可以通过一些前提条件排出一些candidates，比如（2，2）不是candidates，因
为（2，1）肯定要比（2，2）大，那candidate其实最多只有max（m，n）个，一行最多
只能有一个candidate
所以那些candidates组成一个堆，每当一个点确定涂黑以后，把它横坐标或者纵坐标+1
的那些点放入那个heap，这样直到k个
所以复杂度是k log(max(m,n)) | h**k
发帖数: 3368 | 26 你这个算法本质上是在从A[1]+B[1,....,k]和B[1]＋A[1,...,k]中选择k个最大的。
但是实际上有可能A[2]+B[2]>A[1]+B[3] and A[2]+B[2]>A[3]+B[1]
【在 w*****p 的大作中提到】
: greedy。
: 举个例子，
: A ： 10 9 5 3 1
: B ： 8 7 5 3 k 为 5
: 首先， 最大的肯定是 10+8=18
: 然后把A,B换成差额数组， 就是 A[i]-A[i+1]
: 数组变成 1 4 2 2 和 1,1,1,2
: 从这里开始， 选取两个数组中最小的数，并且把另个数组的当前数减去 这个小的数。
: 并且把当前和（初始为18）减去这个小数。这个步骤重复到K次就行了。
: 比如这个例子，第二小的从A里面出，和变成18-1， B的当前数是 1-1=0， 然后A 向后
| l*********y
发帖数: 142 | 27 感觉是对的，但是道理是什么哪?
【在 w*****p 的大作中提到】
: greedy。
: 举个例子，
: A ： 10 9 5 3 1
: B ： 8 7 5 3 k 为 5
: 首先， 最大的肯定是 10+8=18
: 然后把A,B换成差额数组， 就是 A[i]-A[i+1]
: 数组变成 1 4 2 2 和 1,1,1,2
: 从这里开始， 选取两个数组中最小的数，并且把另个数组的当前数减去 这个小的数。
: 并且把当前和（初始为18）减去这个小数。这个步骤重复到K次就行了。
: 比如这个例子，第二小的从A里面出，和变成18-1， B的当前数是 1-1=0， 然后A 向后
| b*****o
发帖数: 715 | 28 “I has 1337 code”上有解答：
http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-
最优解是O(log m+log n),递归的不变量比较巧妙。
int findKthSmallest(int A[], int m, int B[], int n, int k) {
assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);
int i = (int)((double)m / (m+n) * (k-1));
int j = (k-1) - i;
assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);
// invariant: i + j = k-1
// Note: A[-1] = -INF and A[m] = +INF to maintain invariant
int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
int Ai = ((i == m) ? INT_MAX : A[i]);
int Bj = ((j == n) ? INT_MAX : B[j]);
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
assert((Ai > Bj && Ai_1 > Bj) ||
(Ai < Bj && Ai < Bj_1));
// if none of the cases above, then it is either:
if (Ai < Bj)
// exclude Ai and below portion
// exclude Bj and above portion
return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);
else /* Bj < Ai */
// exclude Ai and above portion
// exclude Bj and below portion
return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);
} | i**9
发帖数: 351 | 29 我怎么觉得是 “堆的节点数目最多是”max（m，n）,因为每次只能删一个，而要加入
两个，如果 3*n matrix
3*(n+n 2*n n
3*(2n-1) 2*(n-1) n-1
.
.
.
3*(n) 2 1
那么最大的总在第一列我们每次加入heap第一列的下一个和第二（同行）列中的一个，
那么加完第一列 heap中有 n 个 nodes
是（1，1）
，也就是把一个点确定涂黑以后，就把
最大值的操作
【在 i*********l 的大作中提到】
: 整个算法有点像minimum spanning tree，
: z=x+y是个二维函数。我们从原点开始。有把确定的结果涂黑。第一个涂黑的是（1，1）
: 下一个涂黑的只能是（1，2）或者（2，1），我们只要比较这两个就可以了。假设是（
: 1，2）比较大，那就是（1，2）涂黑。。那下一个candidate只可能在（1，3），（2，
: 1）或者（2，2)，candidate有什么特点呢。就是涂黑的那些点的横坐标或者总坐标加1
: 。而且可以通过一些前提条件排出一些candidates，比如（2，2）不是candidates，因
: 为（2，1）肯定要比（2，2）大，那candidate其实最多只有max（m，n）个，一行最多
: 只能有一个candidate
: 所以那些candidates组成一个堆，每当一个点确定涂黑以后，把它横坐标或者纵坐标+1
: 的那些点放入那个heap，这样直到k个
| h**k
发帖数: 3368 | 30 两道完全不同的题。
【在 b*****o 的大作中提到】
: “I has 1337 code”上有解答：
: http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-
: 最优解是O(log m+log n),递归的不变量比较巧妙。
: int findKthSmallest(int A[], int m, int B[], int n, int k) {
: assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);
:
: int i = (int)((double)m / (m+n) * (k-1));
: int j = (k-1) - i;
: assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);
: // invariant: i + j = k-1
| | | i*********l
发帖数: 766 | 31 其实只需加入一个，因为每一行每一列最多只有一个candidate， 所以min就可以了。
。。
【在 i**9 的大作中提到】
: 我怎么觉得是 “堆的节点数目最多是”max（m，n）,因为每次只能删一个，而要加入
: 两个，如果 3*n matrix
: 3*(n+n 2*n n
: 3*(2n-1) 2*(n-1) n-1
: .
: .
: .
: 3*(n) 2 1
: 那么最大的总在第一列我们每次加入heap第一列的下一个和第二（同行）列中的一个，
: 那么加完第一列 heap中有 n 个 nodes
| z****o
发帖数: 78 | 32 要不就二分吧.
每次猜一个数字d, 用 O(n+m)的时间查到d的rank, 比较是不是比k大,然后继续猜.
若是 int32的话复杂度就是 32*O(n+m) = O(n+m)了的. | c********t
发帖数: 5706 | 33 顶。
但是复杂度好像有问题，比如我只找k=2，也就2个candidates, 不能是2log(min(m,n))
。好像很难算，candidate是求min(x) x(x+1)/2>k.复杂度是 k*log(min（m,n,x)))
是（1，1）
，也就是把一个点确定涂黑以后，就把
最大值的操作
【在 i*********l 的大作中提到】
: 整个算法有点像minimum spanning tree，
: z=x+y是个二维函数。我们从原点开始。有把确定的结果涂黑。第一个涂黑的是（1，1）
: 下一个涂黑的只能是（1，2）或者（2，1），我们只要比较这两个就可以了。假设是（
: 1，2）比较大，那就是（1，2）涂黑。。那下一个candidate只可能在（1，3），（2，
: 1）或者（2，2)，candidate有什么特点呢。就是涂黑的那些点的横坐标或者总坐标加1
: 。而且可以通过一些前提条件排出一些candidates，比如（2，2）不是candidates，因
: 为（2，1）肯定要比（2，2）大，那candidate其实最多只有max（m，n）个，一行最多
: 只能有一个candidate
: 所以那些candidates组成一个堆，每当一个点确定涂黑以后，把它横坐标或者纵坐标+1
: 的那些点放入那个heap，这样直到k个
| j********x
发帖数: 2330 | 34 This is identical (not sure) to the question of finding kth element in a
matrix that is row- & column-sorted.
O(max(m,n)*log(k)) solution is available. Select item from the matrix and
determine its rank in max(m,n) time, which needs to run for log(k) times.
O(k*log(m+n)) solution works by iteratively removing the minimum elements
from the matrix.
No proof or coding, just preliminary thought.
【在 A*********r 的大作中提到】
: you are given 2 arrays sorted in decreasing order of size m and n
: respectively.
: Input: a number k <= n*m and >= 1
: Output: the kth largest sum(a+b) possible. where
: a (any element from array 1)
: b (any element from array 2)
: 如果直接一个一个算的话，从大到小，需要O(k)复杂度。
: 不知道最优解是多少，是O(logk) 还是O(1) ?
: 在careercup上看到的，有人提出来了最优解是O(1), 但是觉得不太对头。。
| s*********b
发帖数: 815 | 35 最优解是O(Mlog(2N/M)):http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no
基本主意是每次把一个matrix划分成四个，然后根据第K个元素的
大致范围抛弃一部分子矩阵。注意每个子矩阵都满足左上角元素最
大右下角元素最小的性质。不过如果不知道这篇论文，从头想的话，
要想出判断准则其实挺难。不过要找出O(logM+logN)的解法还是
比较简单的。就是quickSelect的变种：从左下角出发，总可以线性
地把矩阵分成两块。然后根据K的大小，决定是找上半块还是下半块。
如果是上半块，就用经典的quickSelect搞定，如果是下半块，就继
续划分。这个解法的好处是不需要先生成整个矩阵。在划分矩阵时
即时计算边界就行了。需要的空间无非是保存上半块的边界，也就是
O(M+N)。
举个例子，如果
A = [10, 8, 6, 3, 1]
B = [11, 9, 7, 6, 5]
那么对应的矩阵就是
21, 19, *17*, 14, 12, 11
19, 17, *15*, 12, 10, 9
17, *15*, 13, 10, 8, 7
*16*, 14, 12, 9, 7, 6
*15*, 13, 11, 8, 6, 5
从左下角开始走，因为往坐走总是下降，往上走总是增大，我们可以
轻易知道如果pivot是15的话，这个partition的边界是上面打了*的
元素。这个边界可以按行保存下来，比如用二维数组的话，也就是
[[0, 2], [0, 2], [0, 1], [0, 0], [0, 0]]。所以我们知道上半块有10个
元素。如果K小于10，就用Hoare老大的quickSelect()搞定。如果K
大于10，当然就从13开始，重新划分，其实也就是quickSelect()的
二维变种。 | i**********e
发帖数: 1145 | 36 Your argument doesn't sound convincing to me.
Assuming we are finding the 7th largest element, which is in the first
partition according to your example. To apply QuickSelect, you are assuming
you know the order of the elements in that partition... ie, how could you
tell for sure that the 7th largest element is not in [1,2] or [2,1]???
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********b 的大作中提到】
: 最优解是O(Mlog(2N/M)):http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no
: 基本主意是每次把一个matrix划分成四个，然后根据第K个元素的
: 大致范围抛弃一部分子矩阵。注意每个子矩阵都满足左上角元素最
: 大右下角元素最小的性质。不过如果不知道这篇论文，从头想的话，
: 要想出判断准则其实挺难。不过要找出O(logM+logN)的解法还是
: 比较简单的。就是quickSelect的变种：从左下角出发，总可以线性
: 地把矩阵分成两块。然后根据K的大小，决定是找上半块还是下半块。
: 如果是上半块，就用经典的quickSelect搞定，如果是下半块，就继
: 续划分。这个解法的好处是不需要先生成整个矩阵。在划分矩阵时
: 即时计算边界就行了。需要的空间无非是保存上半块的边界，也就是
| s*********b
发帖数: 815 | 37 QuickSelect不需要知道数据集的顺序啊。用您老的例子吧。K=7，
那我们用左边的分块，也就是[[0,2], [0,2], [0,1], [0, 0], [0, 0]]包
起来的数据。有了这个边界，可一得到分区里所有的和，也就是
S = {21, 19, 17, 19, 17, 15, 17, 15, 16, 15}。QuickSelect是对
这15个元素做的：quickSelect(S, 7) = 16
assuming
【在 i**********e 的大作中提到】
: Your argument doesn't sound convincing to me.
: Assuming we are finding the 7th largest element, which is in the first
: partition according to your example. To apply QuickSelect, you are assuming
: you know the order of the elements in that partition... ie, how could you
: tell for sure that the 7th largest element is not in [1,2] or [2,1]???
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 38 恩，听你这样说就挺有道理。
QuickSelect 的确不用排好序。
虽然我还是不很信服你这方法能 O(log M + log N) 运行，
但是你这方法的确开启了很好的思路。
我稍候再研究研究，并且顺便啃啃书，理解下 QuickSelect 这玩意。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**********e
发帖数: 1145 | 39 对了，听你的解说，似乎要 O(M) 来寻找一个 partition 的边界。
这样达不到你所说的 O( log M + log N ) 复杂度吧.(感觉上是 O(M*N)).
这样挺费时的吧，你能展开说说吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | s*********b
发帖数: 815 | 40 嗯，我想得太仓促了。如果一看到K落在上半块就用传统QuickSelect，
的确是O(MN)。应该是不管K落在哪个partition，都继续
对那个partition做分块，直到找到第K大的和。这样每次都是二分，
平均起来应该是O(log(MN))，也就是O(logM + logN)。当然最坏
情况还是O(MN)。
【在 i**********e 的大作中提到】
: 对了，听你的解说，似乎要 O(M) 来寻找一个 partition 的边界。
: 这样达不到你所说的 O( log M + log N ) 复杂度吧.(感觉上是 O(M*N)).
: 这样挺费时的吧，你能展开说说吗？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| | | l****c
发帖数: 16 | 41 要利用a[i]+b[j]>a[i+1]+b[j]和a[i]+b[j]>a[i]+b[j+1]
heap里面存(a[i]+b[j], i, j)
insert (a[0]+b[0], 0, 0) to heap
for (int l=0; l< k; l++){
get the biggest element (a[i]+b[j], i, j) from heap
if (i+1 < m) insert (a[i+1]+b[j], i+1, j) to heap
if (j+1 < n) insert (a[i]+b[j+1], i, j+1) to heap
} | i**9
发帖数: 351 | 42 还是觉得不太对，要维持一个heap,需要加入相邻的两个才行，所以应该是O(max(m,n))
heap
space
【在 i*********l 的大作中提到】
: 其实只需加入一个，因为每一行每一列最多只有一个candidate， 所以min就可以了。
: 。。
|
|
