r*******k
发帖数: 1423 | 1 m x n的young矩阵
如果m=10^6, n=10^9
普通的那个从右上角的查找方法肯定不行
我想到的是，取最中间那列，找target要被插入的位置，
这样每次可以扔掉一半，递归查找
log(10^15) = 5*8
这样做是ok的么？ | l***i
发帖数: 1309 | 2 这么大的东西不能用一台机器装吧，10^6 G data, even use disk, it is a lot, a
peta integers, you might want to ask how this matrix is stored in disk, and
is that one disk or multiple disks. | r*******k
发帖数: 1423 | 3 我觉得他就是引导我要去按小的那个数的列去查找。
数字可能倒不是很重要。
我现在有点晕
一般young矩阵的查找是(m+n)
那么我这么搞，是o(lgm+lgn)?
感觉不大可能啊。。。
and
【在 l***i 的大作中提到】
: 这么大的东西不能用一台机器装吧，10^6 G data, even use disk, it is a lot, a
: peta integers, you might want to ask how this matrix is stored in disk, and
: is that one disk or multiple disks.
| l***i
发帖数: 1309 | 4 你怎么扔掉一半啊
1 3 5
10 30 50
target = 5 if you throw 3,5,30,50
target = 10 if you throw 1, 3, 10, 30 | r*******k
发帖数: 1423 | 5 target = 5时
5比3大，比30小
可以扔掉 1 3和30 50
剩下5 和 10
【在 l***i 的大作中提到】
: 你怎么扔掉一半啊
: 1 3 5
: 10 30 50
: target = 5 if you throw 3,5,30,50
: target = 10 if you throw 1, 3, 10, 30
|
|
