l*********r
发帖数: 122 | 1 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
(i,j,k) 满足条件A[i]+B[j]+c[k]=1000
这个改怎么做最优？ |
d******b
发帖数: 73 | 2 1000太小，1T太大，所以只要 有三组 1000个桶。然后计数，剩下的就是排列组合问题
了。 |
l*********r
发帖数: 122 | 3 A,B也外排一下
然后binary search？
【在 d******b 的大作中提到】
: 1000太小，1T太大，所以只要 有三组 1000个桶。然后计数，剩下的就是排列组合问题
: 了。
|
o*******r
发帖数: 73 | 4 1T的数字？我觉得可以先去一下重复的，去重复的时候顺便桶排序一下变成一个数出现
多少次。之后要处理的
就很少了。
【在 l*********r 的大作中提到】
: 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
: (i,j,k) 满足条件A[i]+B[j]+c[k]=1000
: 这个改怎么做最优？
|
z*********n
发帖数: 1451 | 5 条件太少了，数据类型是什么？short，integer， long（long）， 这个不同，方法自
然不同。 |
l*********r
发帖数: 122 | 6 都是int类型
【在 z*********n 的大作中提到】
: 条件太少了，数据类型是什么？short，integer， long（long）， 这个不同，方法自
: 然不同。
|
p**r
发帖数: 5853 | 7 这就是个3sum题，
你不用管它大不大，多少T
既然没排序，扫描一遍是跑不掉的。
优化方面可以考虑的是：
#1 先扫描一遍：把的值先排除
#2 去重
然后排序
【在 l*********r 的大作中提到】
: 有3个超大的数组A，B，C，例如每个数组都1T的数据量而且没有排序，要求找出所有的
: (i,j,k) 满足条件A[i]+B[j]+c[k]=1000
: 这个改怎么做最优？
|
z*********n
发帖数: 1451 | 8
int32？
那简单了，不用排序，直接建个表查表就行了，也就1G额外空间--处理3T数据，开了1G
空间，怎么说都不过份吧？
int32也就只能表示4G个unique的数，一个数据集直接开4G bit（500M bytes）的空间
，扫一遍，用第i bit表示i+INT_MIN这个int在数据集中存在与否。也就是用500M空间
表示了1T数据，而且还能O（1）时间查询一个整数存在与否。
懒得继续码字了，这个字典都给建好了，剩下的该怎么做应该不用多废话了吧。
【在 l*********r 的大作中提到】
: 都是int类型
|
l*********r
发帖数: 122 | 9 double 咋整？
1G
【在 z*********n 的大作中提到】
:
: int32？
: 那简单了，不用排序，直接建个表查表就行了，也就1G额外空间--处理3T数据，开了1G
: 空间，怎么说都不过份吧？
: int32也就只能表示4G个unique的数，一个数据集直接开4G bit（500M bytes）的空间
: ，扫一遍，用第i bit表示i+INT_MIN这个int在数据集中存在与否。也就是用500M空间
: 表示了1T数据，而且还能O（1）时间查询一个整数存在与否。
: 懒得继续码字了，这个字典都给建好了，剩下的该怎么做应该不用多废话了吧。
|
z*********n
发帖数: 1451 | 10
我是不是提前先问你这是啥数据类型了？
是不是说了不同类型手法不一样。
然后你告诉我是int
我码了七行字解了后你啥别的不说只回仨字“double咋整”？
自己琢磨吧。
【在 l*********r 的大作中提到】
: double 咋整？
:
: 1G
|
|
|
H**********5
发帖数: 2012 | 11 非double和double难度完全不是一个数量级，可以另外开一贴
: double 咋整？
: 1G
【在 l*********r 的大作中提到】
: double 咋整？
:
: 1G
|
c********t
发帖数: 5706 | 12 bitmap怎么处理重复数据？
1G
【在 z*********n 的大作中提到】
:
: 我是不是提前先问你这是啥数据类型了？
: 是不是说了不同类型手法不一样。
: 然后你告诉我是int
: 我码了七行字解了后你啥别的不说只回仨字“double咋整”？
: 自己琢磨吧。
|
z*********n
发帖数: 1451 | 13
天然去重啊？还需要如何处理。
【在 c********t 的大作中提到】
: bitmap怎么处理重复数据？
:
: 1G
|
l*********r
发帖数: 122 | 14 大牛，失礼失礼...
还在消化你的解法。。。
【在 z*********n 的大作中提到】
:
: 天然去重啊？还需要如何处理。
|
c********t
发帖数: 5706 | 15 题目要求找出所有的(i,j,k) 满足条件A[i]+B[j]+c[k]=1000
【在 z*********n 的大作中提到】
:
: 天然去重啊？还需要如何处理。
|
