第一大数字矩阵中最大的产品，速度很快
我正在研究一种可以处理大量项目的排序/排序算法，并且需要以高效的方式实现以下算法以使其工作：
有两个数字列表。 它们同样长，约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，这两者都比较大。 所以你不能只看两个邻居，但你必须回溯。
我认为可以在O(n log n + n log m) 。 这是我的算法的草图，我认为它会起作用。 这有点粗糙。
O(m log m) ） O(m log m) ） s为min(m, n) 。 （以O(1) ） s懒惰序列迭代器L[0]通过L[s-1] L[i]将遍历s值A[i]*B[0] ， A[i]*B[1] ，...， A[i]*B[s-1] 。 （需要O(s) ） q 。 迭代器将根据其当前值进行优先级排序。 （需要O(s)因为最初他们已经在为了） q提取n值。 最后一个值将是所需的结果。 当一个迭代器被拉动时，它将被重新插入到q使用它的下一个值作为新的优先级。 如果迭代器已经耗尽，请不要重新插入它。 （需要O(n log s) ） 总之，这个算法将采用O(m log m + (s + n)log s) ，但s等于m或n 。
我不认为有一个O（f（n））的算法，它与m无关。
但是有一个相对较快的O（n * logm）算法：
首先对两个数组进行排序，得到A [0]> A [1]> ...> A [m-1]和B [0]> B [1]> ...> B [m- 1]。 （当然，这是O（mlogm）。）
然后我们建立一个最大堆，其元素是A [0] * B [0]，A [0] * B [1]，... A [0] * B [m-1]。 我们维护一个“指针数组”P [0]，P [1]，... P [m-1]。 P [i] = x意味着B [i] * A [x]当前在堆中。 所有P [i]最初都是零。
在每次迭代中，我们从堆中弹出最大元素，这是下一个最大的产品。 假设它来自B [i] * A [P [i]]（我们可以记录来自哪个B [i]的堆中的元素），然后我们向前移动相应的指针：P [i] + = 1，并将新的B [i] * A [P [i]]推入堆中。 （如果P [i]移到超出范围（> = m），我们只需将-inf推入堆中。）
第n次迭代后，我们得到第n个最大的产品。
有n次迭代，每次迭代都是O（logm）。
编辑：添加一些细节
你不需要对这50万个元素进行排序来获得前3名。
只需取前3，将它们放入SortedList中，然后迭代列表，用新值替换3个元素中最小的元素（如果更高），然后使用结果列表。
对这两个列表执行此操作，并且以3 * 3矩阵结束，应该很容易取第3个值。
这是一个在scala中的实现。
如果我们假设n小于m，并且A = [1,3,4]并且B = [2,2,5]，则n = 2：
你会拿（3，4）=>对它们进行排序（4,3）
然后取（2,5）=>对它们进行排序（5,2）
你现在可以做一个压缩搜索。 当然，现在最大的产品是（5，4）。 但下一个是（4 * 2）或（5 * 3）。 对于更长的列表，你可以记住4 * 2的结果是什么，只将它与下一个产品进行比较，然后采取其他方式。 这样你就只能计算一个产品太多。
链接地址: http://www.djcxy.com/p/59459.html