我正在研究一种可以处理大量项目的排序/排序算法,我需要以有效的方式实现以下算法才能使其工作:
有两个数字列表.它们同样长,约100-500万件.从这里我需要找到这些列表之间的第n大产品,即.如果您创建一个矩阵,其中顶部有一个列表,那么您有另一个列表,每个单元格是上面的数字和侧面的数字的乘积.
示例:列表是A=[1, 3, 4]和B=[2, 2, 5].那么产品就是[2, 2, 5, 6, 6, 15, 8, 8, 20].如果我想要第三大,那就是8.
天真的解决方案是简单地生成这些数字,对它们进行排序然后选择第n个最大数字.但那就是O(m^2 * log m^2)m是小列表中元素的数量,而这个数字还不够快.
我认为我需要的是先对两个小清单进行排序.那是O(m * log m).然后我肯定知道最大的一个A [0]*B [0].第二大的是A [0]*B [1]或A [1]*B [0],......
我觉得这可以O(f(n))分步进行,与矩阵的大小无关.但我无法找到一种有效的方法来完成这一部分.
编辑:有一个被删除的答案,建议记住两个有序集合中的位置,然后查看A [a]*B [b + 1]和A [a + 1]*B [b],返回更大的一个并递增a/b.我会在删除之前发布此评论:
这不行.想象一下两个列表A = B = [3,2,1].这将给你像[9,6,3; 6,4,2; 3,2,1].所以你从(0,0)= 9开始,转到(0,1)= 6然后选择是(0,2)= 3或(1,1)= 4.但是,这将错过(1,0)= 6,这比两者都大.所以你不能只看两个邻居,但你必须回溯.