我正在研究一个与大量项目一起使用的排序/排名算法,我需要有效地实现以下算法才能使其正常工作:
有两个数字列表。它们长度相等,约为10-50万项。从这里我需要在这些列表之间找到第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,它比两者都大。因此,您不能只看两个邻居,而必须回溯。
有两个数字列表。它们长度相等,约为10-50万项。从这里我需要在这些列表之间找到第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,它比两者都大。因此,您不能只看两个邻居,而必须回溯。