x*t
2 楼
比如我有2个数组，每个数组4个元素。
每个数组里的数组元素都是从大到小排列的
a[0]>a[1]>a[2]>a[3]
b[0]>b[1]>b[2]>b[3]
各种组合有16个,
a[0]*b[0], a[0]*b[1], a[0]*b[2], a[0]*b[3]
a[1]*b[0], a[1]*b[1], a[1]*b[2], a[1]*b[3]
a[2]*b[0], a[2]*b[1], a[2]*b[2], a[2]*b[3]
a[3]*b[0], a[3]*b[1], a[3]*b[2], a[3]*b[3]
我只想取以上16种组合中，值最大的6种组合，但是我又不想把16个值全部都算出来再
比较大小。。。。
理由是，如果我有M个数组，每个数组N个元素，全部组合就有N^M.M太大，计算量太大
，希望有什么办法可以只计算我需要的组合。。。。
请指教，多谢！！！
每个数组里的数组元素都是从大到小排列的
a[0]>a[1]>a[2]>a[3]
b[0]>b[1]>b[2]>b[3]
各种组合有16个,
a[0]*b[0], a[0]*b[1], a[0]*b[2], a[0]*b[3]
a[1]*b[0], a[1]*b[1], a[1]*b[2], a[1]*b[3]
a[2]*b[0], a[2]*b[1], a[2]*b[2], a[2]*b[3]
a[3]*b[0], a[3]*b[1], a[3]*b[2], a[3]*b[3]
我只想取以上16种组合中，值最大的6种组合，但是我又不想把16个值全部都算出来再
比较大小。。。。
理由是，如果我有M个数组，每个数组N个元素，全部组合就有N^M.M太大，计算量太大
，希望有什么办法可以只计算我需要的组合。。。。
请指教，多谢！！！
s*e
3 楼
你的数据有什么assumption吗？如果都是正数就好办，
如果正负都有的话就比较麻烦了
【在 x****t 的大作中提到】
: 比如我有2个数组，每个数组4个元素。
: 每个数组里的数组元素都是从大到小排列的
: a[0]>a[1]>a[2]>a[3]
: b[0]>b[1]>b[2]>b[3]
: 各种组合有16个,
: a[0]*b[0], a[0]*b[1], a[0]*b[2], a[0]*b[3]
: a[1]*b[0], a[1]*b[1], a[1]*b[2], a[1]*b[3]
: a[2]*b[0], a[2]*b[1], a[2]*b[2], a[2]*b[3]
: a[3]*b[0], a[3]*b[1], a[3]*b[2], a[3]*b[3]
: 我只想取以上16种组合中，值最大的6种组合，但是我又不想把16个值全部都算出来再
如果正负都有的话就比较麻烦了
【在 x****t 的大作中提到】
: 比如我有2个数组，每个数组4个元素。
: 每个数组里的数组元素都是从大到小排列的
: a[0]>a[1]>a[2]>a[3]
: b[0]>b[1]>b[2]>b[3]
: 各种组合有16个,
: a[0]*b[0], a[0]*b[1], a[0]*b[2], a[0]*b[3]
: a[1]*b[0], a[1]*b[1], a[1]*b[2], a[1]*b[3]
: a[2]*b[0], a[2]*b[1], a[2]*b[2], a[2]*b[3]
: a[3]*b[0], a[3]*b[1], a[3]*b[2], a[3]*b[3]
: 我只想取以上16种组合中，值最大的6种组合，但是我又不想把16个值全部都算出来再
x*t
4 楼
就先说说都是正数的情况好了。。。多谢！
【在 s******e 的大作中提到】
: 你的数据有什么assumption吗？如果都是正数就好办，
: 如果正负都有的话就比较麻烦了
【在 s******e 的大作中提到】
: 你的数据有什么assumption吗？如果都是正数就好办，
: 如果正负都有的话就比较麻烦了
s*e
5 楼
全部都是正的还不好办，既然都是排好序的，
就再merge sort一下，然后从头开始取最大的pairs...
【在 x****t 的大作中提到】
: 就先说说都是正数的情况好了。。。多谢！
就再merge sort一下，然后从头开始取最大的pairs...
【在 x****t 的大作中提到】
: 就先说说都是正数的情况好了。。。多谢！
x*t
6 楼
谢谢，但是还是不太明白，这样的话，还是要把所有的组合都算一遍，然后取前几个我
要的？
如果有N个数组的话，4^N的各种组合，运算量会很大。。。
有没有可能某种算法减少这种运算量？
【在 s******e 的大作中提到】
: 全部都是正的还不好办，既然都是排好序的，
: 就再merge sort一下，然后从头开始取最大的pairs...
要的？
如果有N个数组的话，4^N的各种组合，运算量会很大。。。
有没有可能某种算法减少这种运算量？
【在 s******e 的大作中提到】
: 全部都是正的还不好办，既然都是排好序的，
: 就再merge sort一下，然后从头开始取最大的pairs...
s*e
7 楼
当然不需要把所有的组合算过了，只需要对排好序的
前几个进行乘法就可以了。建议你自己动手试试看
先把这些数组merge sort以后看看是什么样子的
【在 x****t 的大作中提到】
: 谢谢，但是还是不太明白，这样的话，还是要把所有的组合都算一遍，然后取前几个我
: 要的？
: 如果有N个数组的话，4^N的各种组合，运算量会很大。。。
: 有没有可能某种算法减少这种运算量？
前几个进行乘法就可以了。建议你自己动手试试看
先把这些数组merge sort以后看看是什么样子的
【在 x****t 的大作中提到】
: 谢谢，但是还是不太明白，这样的话，还是要把所有的组合都算一遍，然后取前几个我
: 要的？
: 如果有N个数组的话，4^N的各种组合，运算量会很大。。。
: 有没有可能某种算法减少这种运算量？
j*k
8 楼
上次有人就说用merge sort
【在 s******e 的大作中提到】
: 当然不需要把所有的组合算过了，只需要对排好序的
: 前几个进行乘法就可以了。建议你自己动手试试看
: 先把这些数组merge sort以后看看是什么样子的
【在 s******e 的大作中提到】
: 当然不需要把所有的组合算过了，只需要对排好序的
: 前几个进行乘法就可以了。建议你自己动手试试看
: 先把这些数组merge sort以后看看是什么样子的
o*o
9 楼
there is no group like a[x]*a[y], how could you merge them together?
【在 s******e 的大作中提到】
: 当然不需要把所有的组合算过了，只需要对排好序的
: 前几个进行乘法就可以了。建议你自己动手试试看
: 先把这些数组merge sort以后看看是什么样子的
【在 s******e 的大作中提到】
: 当然不需要把所有的组合算过了，只需要对排好序的
: 前几个进行乘法就可以了。建议你自己动手试试看
: 先把这些数组merge sort以后看看是什么样子的
P*e
10 楼
I think he meant:
Original:
a1,a2,a3
b1,b2,b3
After merge:
c1,c2,c3,c4,c5,c6
a1...............
say 3 smallest:
for i,j from 0
if(i == j) do
j++;
if (ci and cj belong to the same original array) do
compare( ci+1 * cj and ci*cj+1)
increment i or j, which is smaller
output ci*cj
【在 o*o 的大作中提到】
: there is no group like a[x]*a[y], how could you merge them together?
Original:
a1,a2,a3
b1,b2,b3
After merge:
c1,c2,c3,c4,c5,c6
a1...............
say 3 smallest:
for i,j from 0
if(i == j) do
j++;
if (ci and cj belong to the same original array) do
compare( ci+1 * cj and ci*cj+1)
increment i or j, which is smaller
output ci*cj
【在 o*o 的大作中提到】
: there is no group like a[x]*a[y], how could you merge them together?
i*g
11 楼
set a decreasing-sorted array c initially with all -Inf's,
for each i
for each j
if a[i]*b[j] is greater than the last element in array c
insert a[i]*b[j] into c;
for each i
for each j
if a[i]*b[j] is greater than the last element in array c
insert a[i]*b[j] into c;
c*n
12 楼
ordered products:
a[0]*b[0]
a[1]*b[0], a[0]*b[1]
a[1]*b[1]
a[1]*b[2],a[2]*b[1]
...
where ',' means unordered. return as soon as you get enough products that
covers the number of products you need. Then, in the last/ least group,
perform whatever sort that's fast. You are all set!
a[0]*b[0]
a[1]*b[0], a[0]*b[1]
a[1]*b[1]
a[1]*b[2],a[2]*b[1]
...
where ',' means unordered. return as soon as you get enough products that
covers the number of products you need. Then, in the last/ least group,
perform whatever sort that's fast. You are all set!
相关阅读
对J2EE的几个迷惑use abort() to generate coredump (转载)借人气问一个boost的问题，linux上生成的binary archive (转载)有人做图像识别或者OCR的吗？C++是给神仙用的语言Clojure/West的会场几乎没有什么中国人越简单的语言从历史的角度越好包子答谢！！请教cyber-security哪些学校比较强？ (转载)问问这里的大神，architect能自学成才吗？C嵌入式一个问题：SanDisk CF APIzhaoce: 我感觉python很有前途呀前一段在这里说要写 tax 程序的进展怎么样了？？LinkedIn統計 (2013年五月)Looks like 王垠 was right about Google culture要具备这些能力，应该看哪些方面的书？学会python能找到工作吗大家讨论一下其他语言需要Spring这种东西吗？关于ruby和rails一点疑惑functional programming?Twitter統計 (2013年三月)