我终于明白了 - 未名空间MITBBS历史存档

A*r2010-03-15 07:03

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), 但是觉得不太对头。。

p*92010-03-15 07:03

2 楼

上海籍少妇遭洋老公殴打致瘫坐轮椅越洋作供(图)
2013年05月14日19:58:03 [新闻大杂烩]
结婚半年的少妇倪金英(Jin Ying Ni，译音)，去年1月疑在家中遭人撞落楼梯，导致
腰椎粉碎性骨折，她控告贾马克（Mark Jia, 译音）严重殴打罪，被告昨在温市省级法
院否认控罪。Mitbbs.com
倪金英和贾马克现年都是29岁，被告在亲友陪同下出席在温市缅街的省级法院聆讯。而
原诉人倪金英现时身在中国上海，她腰部以下瘫痪，需要坐轮椅，昨天透过视像方式作
供。Mitbbs.com
腰椎粉碎性骨折Mitbbs.com
控方代表律师坎宁安（Sandra Cunningham）在庭上指出，去年1月14日，贾马克从1米
高的地方跳下压在倪金英身上，令受害人腰椎粉碎性骨折。Mitbbs.com
倪金英作证时说，当她被丈夫压在地下后，双腿没有感觉，她乞求贾马克打911报警，
贾马克却再次抓住她的肩膀，强行拉她起来，殴打她的背部和颈部。Mitbbs.com
倪金英说：「我告诉他(贾马克)，我感觉像死了似的。」在视像期间，倪金英似穿着睡
衣，一直坐在书桌上，面对着一部手提电脑，并且要靠枕头支撑身体。Mitbbs.com
而被告身穿紫色衬衫，灰色长裤，戴着眼镜，与律师坐在庭上聆听坎宁安与倪金英的证
词，贾马克的10多位亲友，包括他母亲则坐在旁听席上。Mitbbs.com
由于这是第一天的聆讯，控方律师用了很多时间在瞭解，被告与妻子婚后共同居住在温
市西53街（W. 53rd Ave.）700号路段独立屋的内部陈设，包括厨房、书房、睡房等位
置，甚至楼梯与大门的距离都逐一询问。倪金英说，她于2002年到加拿大，在卑诗内陆
读书，后又到温哥华就读，2010年10月23日与贾马克结婚，2011年7月23日办仪式，同
年10月10日在上海补办结婚仪式，其后贾马克就经常暴力对待她。Mitbbs.com
倪金英指出2011年11月18日、11月25日和12月3日等发生家暴，其中，12月3日又为了参
加一个朋友的派对问题，遭到贾马克严重殴打。除了倪金英拟请控方指控贾马克1项蓄
意伤人罪外，控方还加控被告5项伤人罪名，聆讯将在周二、周四、周五和下周二及周
三继续。Mitbbs.com

b*t2010-03-15 07:03

3 楼

绵绵每晚腻歪着和我挤一个枕头，不是因为爱我，其实是因为爱上了我的枕头。
我不在床上的时候，绵绵可高兴了，一直睡在枕头上，终于可以独自一猫霸占了。
有点伤心。

r*u2010-03-15 07:03

4 楼

直接算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), 但是觉得不太对头。。

p*92010-03-15 07:03

5 楼

感觉涉外婚姻中的家暴很多啊，上次看韦唯接受采访她和前夫也是这个问题。

【在 p**********9 的大作中提到】

: 上海籍少妇遭洋老公殴打致瘫坐轮椅越洋作供(图)
: 2013年05月14日19:58:03 [新闻大杂烩]
: 结婚半年的少妇倪金英(Jin Ying Ni，译音)，去年1月疑在家中遭人撞落楼梯，导致
: 腰椎粉碎性骨折，她控告贾马克（Mark Jia, 译音）严重殴打罪，被告昨在温市省级法
: 院否认控罪。Mitbbs.com
: 倪金英和贾马克现年都是29岁，被告在亲友陪同下出席在温市缅街的省级法院聆讯。而
: 原诉人倪金英现时身在中国上海，她腰部以下瘫痪，需要坐轮椅，昨天透过视像方式作
: 供。Mitbbs.com
: 腰椎粉碎性骨折Mitbbs.com
: 控方代表律师坎宁安（Sandra Cunningham）在庭上指出，去年1月14日，贾马克从1米

h*e2010-03-15 07:03

6 楼

haha
你终于悟了！
我家小黑每天跟我挤一个被窝也不是因为爱我，而是爱被窝的缓和。这不冬天刚过完，
人家立马不钻被窝了。。。

【在 b***t 的大作中提到】

: 绵绵每晚腻歪着和我挤一个枕头，不是因为爱我，其实是因为爱上了我的枕头。
: 我不在床上的时候，绵绵可高兴了，一直睡在枕头上，终于可以独自一猫霸占了。
: 有点伤心。

h*k2010-03-15 07:03

7 楼

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), 但是觉得不太对头。。

H*r2010-03-15 07:03

8 楼

外F

x*u2010-03-15 07:03

9 楼

你这反应也忒慢了

b*n2010-03-15 07:03

10 楼

O(KlogK)是用的heap吧?
这个题的变形是一个数组,找最小/大的K个pairs.

【在 h**k 的大作中提到】

: O(k)的算法极其复杂，发表过一篇论文。比较简单的是O(klogk)的复杂度。

f*g2010-03-15 07:03

11 楼

干嘛不一开始就离婚了，为什么忍受那么久？

【在 p**********9 的大作中提到】

: 感觉涉外婚姻中的家暴很多啊，上次看韦唯接受采访她和前夫也是这个问题。

i*i2010-03-15 07:03

12 楼

哼，我家酱就是跟我，我不在家人家不上床

b*r2010-03-15 07:03

13 楼

应该是O(k)
两个sorted数组 a和b
a[0]+b[0]一定是最大的 a[0]+b[1] and a[1]+b[0]谁第二大不一定比一下然后挪a或者b的index
不过比较麻烦 code没写出来...

b*t2010-03-15 07:03

14 楼

我不是还相信猫有纯真的爱情么，呜呜

l*o2010-03-15 07:03

15 楼

有可能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没写出来...

h*e2010-03-15 07:03

16 楼

那是因为你是天然暖炉。。。

【在 i*****i 的大作中提到】

: 哼，我家酱就是跟我，我不在家人家不上床

b*r2010-03-15 07:03

17 楼

用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(iif(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];

i*i2010-03-15 07:03

18 楼

偶家ld胖胖啊，比我暖才对：）

【在 h******e 的大作中提到】

: 那是因为你是天然暖炉。。。

b*r2010-03-15 07:03

19 楼

不可能条件
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

c*e2010-03-15 07:03

20 楼

胖子只是自己暖而已
隔层脂肪，外皮就是凉凉的
还是瘦子摸起来暖阿

【在 i*****i 的大作中提到】

: 偶家ld胖胖啊，比我暖才对：）

A*r2010-03-15 07:03

21 楼

能简单说一下四个指针的意义么？

【在 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;

o*l2010-03-15 07:03

22 楼

lol
that's so cute

【在 b***t 的大作中提到】

: 绵绵每晚腻歪着和我挤一个枕头，不是因为爱我，其实是因为爱上了我的枕头。
: 我不在床上的时候，绵绵可高兴了，一直睡在枕头上，终于可以独自一猫霸占了。
: 有点伤心。

A*r2010-03-15 07:03

23 楼

那个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*R2010-03-15 07:03

24 楼

哈哈，我的猫猫我不在的时候不上我床的，看来是爱我不是爱床了(BSO)

【在 b***t 的大作中提到】

: 绵绵每晚腻歪着和我挤一个枕头，不是因为爱我，其实是因为爱上了我的枕头。
: 我不在床上的时候，绵绵可高兴了，一直睡在枕头上，终于可以独自一猫霸占了。
: 有点伤心。

A*r2010-03-15 07:03

25 楼

这个算法是错的，四个指针其中两个是主指针，分别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;

s*M2010-03-15 07:03

26 楼

给你个解心结的。。。
绵绵爱上枕头，是因为有你的味道啊~~~~~~

A*r2010-03-15 07:03

27 楼

我找了好久，没有找到正确的O(k)的算法。。
如果用max heap,把后两个可能最大sum都放进去,估计能达到O（klogk),不过用c写起来
也不简单的样子..

【在 h**k 的大作中提到】

: O(k)的算法极其复杂，发表过一篇论文。比较简单的是O(klogk)的复杂度。

A*R2010-03-15 07:03

28 楼

that's a good point...

【在 s******M 的大作中提到】

: 给你个解心结的。。。
: 绵绵爱上枕头，是因为有你的味道啊~~~~~~

r*u2010-03-15 07:03

29 楼

能不能解释一下klogk的算法

【在 A*********r 的大作中提到】

: 我找了好久，没有找到正确的O(k)的算法。。
: 如果用max heap,把后两个可能最大sum都放进去,估计能达到O（klogk),不过用c写起来
: 也不简单的样子..

y*u2010-03-15 07:03

30 楼

你俩同性

【在 b***t 的大作中提到】

: 我不是还相信猫有纯真的爱情么，呜呜

b*r2010-03-15 07:03

31 楼

是不对再想想啊

【在 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)大。。

t*u2010-03-15 07:03

32 楼

………………还是shampoo的味道？

【在 s******M 的大作中提到】

: 给你个解心结的。。。
: 绵绵爱上枕头，是因为有你的味道啊~~~~~~

b*r2010-03-15 07:03

33 楼

对啊为什么不是(n+m)lg(n+m)呢

【在 r***u 的大作中提到】

:
: 能不能解释一下klogk的算法

m*O2010-03-15 07:03

34 楼

cmft cmft...
说不定是喜欢姐姐的味道！

【在 b***t 的大作中提到】

: 绵绵每晚腻歪着和我挤一个枕头，不是因为爱我，其实是因为爱上了我的枕头。
: 我不在床上的时候，绵绵可高兴了，一直睡在枕头上，终于可以独自一猫霸占了。
: 有点伤心。

x*32010-03-15 07:03

35 楼

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*r2010-03-15 07:03

36 楼

你是说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*u2010-03-15 07:03

37 楼

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*32010-03-15 07:03

38 楼

是的
k = O(m*n)

【在 r**u 的大作中提到】

: build (m*n-k)-min-heap --> complexity is O(m*n)

x*32010-03-15 07:03

39 楼

感觉很有戏，搬个椅子等paul大虾给解法

w*p2010-03-15 07:03

40 楼

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*p2010-03-15 07:03

41 楼

从这里开始，选取两个数组中当前（指针从头开始）最小的数(就比较 a[i] 和 b[j],
i 和 j 是当前指针，index or whatever)，并且把另个数组的当前数减去这个小的
数。
并且把当前和（初始为18）减去这个小数。这个步骤重复到K次就行了。

e*r2010-03-15 07:03

42 楼

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*a2010-03-15 07:03

43 楼

我感觉这个不对啊。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*l2010-03-15 07:03

44 楼

整个算法有点像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*k2010-03-15 07:03

45 楼

你这个算法本质上是在从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*y2010-03-15 07:03

46 楼

感觉是对的，但是道理是什么哪?

【在 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*o2010-03-15 07:03

47 楼

“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*92010-03-15 07:03

48 楼

我怎么觉得是 “堆的节点数目最多是”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*k2010-03-15 07:03

49 楼

两道完全不同的题。

【在 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*l2010-03-15 07:03

50 楼

其实只需加入一个，因为每一行每一列最多只有一个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*o2010-03-15 07:03

51 楼

要不就二分吧.
每次猜一个数字d, 用 O(n+m)的时间查到d的rank, 比较是不是比k大,然后继续猜.
若是 int32的话复杂度就是 32*O(n+m) = O(n+m)了的.

c*t2010-03-15 07:03

52 楼

顶。
但是复杂度好像有问题，比如我只找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*x2010-03-15 07:03

53 楼

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*b2010-03-15 07:03

54 楼

最优解是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*e2010-03-15 07:03

55 楼

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*b2010-03-15 07:03

56 楼

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*e2010-03-15 07:03

57 楼

恩，听你这样说就挺有道理。
QuickSelect 的确不用排好序。
虽然我还是不很信服你这方法能 O(log M + log N) 运行，
但是你这方法的确开启了很好的思路。
我稍候再研究研究，并且顺便啃啃书，理解下 QuickSelect 这玩意。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*e2010-03-15 07:03

58 楼

对了，听你的解说，似乎要 O(M) 来寻找一个 partition 的边界。
这样达不到你所说的 O( log M + log N ) 复杂度吧.(感觉上是 O(M*N)).
这样挺费时的吧，你能展开说说吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

s*b2010-03-15 07:03

59 楼

嗯，我想得太仓促了。如果一看到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*c2010-03-15 07:03

60 楼

要利用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*92010-03-15 07:03

61 楼

还是觉得不太对，要维持一个heap,需要加入相邻的两个才行，所以应该是O(max(m,n))
heap
space

【在 i*********l 的大作中提到】

: 其实只需加入一个，因为每一行每一列最多只有一个candidate，所以min就可以了。
: 。。