我有两个列表。列表
给定一个小的正数
请注意,列表
我们如何有效地设计算法来解决这个问题?我在考虑对列表
更新:目前我已经想出了一些低效但正确的解决方案:首先对' L1 '进行排序。将'L1'分成两个块:一个块是前N-1个元素,另一个块是最后一个元素。假设最佳的
L1
包含所有正整数,列表L2
包含正数(例如0.01、0.1、0.5、3、5、10、100....)
。给定一个小的正数
M
(例如0.10948472)
,从L1
中找到a,b
和从L2
中找到c
,使得(b/a)*c
最大化但仍然<=M
。请注意,列表
L2
是固定的(长度大约为7000
),列表L1
具有可变长度(可以具有单个元素或多达3000
个元素)。我们如何有效地设计算法来解决这个问题?我在考虑对列表
L1
使用分治方法将其分成两部分再合并,但没有成功。有没有人可以高效地解决它?更新:目前我已经想出了一些低效但正确的解决方案:首先对' L1 '进行排序。将'L1'分成两个块:一个块是前N-1个元素,另一个块是最后一个元素。假设最佳的
a,b,c
已经在L1
的前N-1
个元素中找到,我将检查是否可以在第一个块中找到一些a
和第二个块中找到b
(仅一个元素)以及一些c
,使得(b/a)*c
更好。由于我必须循环遍历L2
中的每个元素,尽管它是nlogn,但仍然显得很慢。
b/a
和d/c
数组并对它们进行排序,以O((n^2) * log(n^2))
的时间复杂度完成。你想要实现什么样的时间复杂度? - dWinder