python - 如何有效地找出低于阈值的最大值？

Question

我有两个列表。列表L1包含所有正整数，列表L2包含正数 (e.g. 0.01,0.1,0.5,3,5,10,100....) .

给定一个小正数 M (e.g. 0.10948472) , 找到 a,b来自 L1 和 c来自 L2英石。 (b/a)*c最大化但仍然是<=M

请注意列表 L2是固定的(长度在 7000 左右)，列出 L1具有可变长度(可以包含单个元素或最多 3000 个元素)。

我们如何才能有效地设计算法来解决这个问题？我正在考虑在列表 L1 上使用分而治之把它分成两部分然后结合起来，但没有成功。谁能高效解决？

更新:目前我制定了一些低效但正确的解决方案:首先对“L1”进行排序。将“L1”分成两个 block :一个 block 是第一个 N-1元素，另一个 block 是最后一个元素。假设最好a,b,c已在第一个N-1上找到L1 的元素, 我检查我们是否可以找到一些 a在第一 block 和b在第二 block (只有一个元素)和一些 c , 这样 (b/a)*c改善。因为我必须遍历 L2 中的每个元素，虽然是nlogn，还是显得很慢

Answer 1

这个问题是3SUM-hard ，所以你不太可能比 Theta(n^2) 做得更好。如果我没理解错的话，你目前的算法是 O(n^2 log n)，这并没有留下很大的改进空间。