如何有效地找出低于阈值的最大值？
How to efficiently find out the maximum value below a threshold?
我有两个列表。列表 L1 包含所有正整数，列表 L2 包含正数 (e.g. 0.01,0.1,0.5,3,5,10,100....).
给定一个小的正数 M (e.g. 0.10948472)，从 L1 中找到 a,b 并从 L2 s.t 中找到 c。 (b/a)*c 已最大化但仍然 <=M
请注意，列表 L2 是固定的（长度在 7000 左右），列表 L1 的长度可变（可以包含单个元素或最多 3000 个元素）。
我们如何才能有效地设计算法来解决这个问题？我正在考虑在列表 L1 上使用分而治之将其分成两部分然后合并，但没有成功。谁能高效解决？
更新：目前我制定了一些低效但正确的解决方案：首先对 'L1' 进行排序。将 'L1' 分成两块：一个块是前 N-1 个元素，另一个块是最后一个元素。假设在 L1 的前 N-1 个元素上找到了最好的 a,b,c，我检查是否可以在第一个块中找到一些 a 并在第二个块中找到 b （仅一个元素）和一些 c，这样 (b/a)*c 会有所改善。由于我必须遍历 L2 中的每个元素，尽管它是 nlogn，但仍然显得很慢
这个问题是 3SUM-hard，所以你不太可能比 Theta(n^2) 做得更好。如果我没理解错的话，你现在的算法是O(n^2 log n)，没有留下很大的改进空间。
据我了解，对于给定的 a/b 组合，您不必遍历 L2 的每个元素。 L2 升序排列。然后假设您从 L1 中选择 a/b 的第一个组合。对于 c，您可以选择 L2 中间的元素，即索引 3500 处的元素并乘以 a/b。如果答案小于 M，您可以选择更高索引处的元素，例如 7000*3/4，即 5250。如果答案仍然更少，则继续更高。相反，如果 (a/b)*c 超过 M，则选择一个较低的索引。您可以收敛到特定 a/b 组合的 c 的最大值。
P.S。不用说，在对 L1 和 L2 进行排序后，您可以添加一个 if 语句来消除 L1 或 L2 中的那些元素，这些元素分别对于 L2 或 L1 的任何值总是超过 M。
升序排列 L1。假设|L1| = n。这是 O(n log n)。
对于 L2 中的每个元素（等式中的 'c'），执行以下操作（因此 O(1) 次，因为 L2 是固定的）。
1. For the first element in L1 (which we'll treat as the 'a' in the equation), use binary search on L1 to find a second element (the 'b') s.t. (b/a)*c is maximized but still <=M.
2. Now, we'll move on to the next element in L1. Note that we're increasing the denominator, so the numerator will either stay the same or increase. We'll just iterate rather than using binary search.
3. repeat step 2.
在第 2 步和第 3 步中，我们会跟踪迄今为止为 a、b 和 c 找到的最佳值。
运行 时间：O(n log n) 进行排序，然后在第 2 步中，我们只从每个值递增一次分子或分母，所以这是 O(n) + O(n) = O(n).
这利用了 L2 的固定优势。如果 |L2|=m 且 m 不固定，则需要 O(n log n) + O(m*n)
我有两个列表。列表 L1 包含所有正整数，列表 L2 包含正数 (e.g. 0.01,0.1,0.5,3,5,10,100....).
给定一个小的正数 M (e.g. 0.10948472)，从 L1 中找到 a,b 并从 L2 s.t 中找到 c。 (b/a)*c 已最大化但仍然 <=M
请注意，列表 L2 是固定的（长度在 7000 左右），列表 L1 的长度可变（可以包含单个元素或最多 3000 个元素）。
我们如何才能有效地设计算法来解决这个问题？我正在考虑在列表 L1 上使用分而治之将其分成两部分然后合并，但没有成功。谁能高效解决？
更新：目前我制定了一些低效但正确的解决方案：首先对 'L1' 进行排序。将 'L1' 分成两块：一个块是前 N-1 个元素，另一个块是最后一个元素。假设在 L1 的前 N-1 个元素上找到了最好的 a,b,c，我检查是否可以在第一个块中找到一些 a 并在第二个块中找到 b （仅一个元素）和一些 c，这样 (b/a)*c 会有所改善。由于我必须遍历 L2 中的每个元素，尽管它是 nlogn，但仍然显得很慢
这个问题是 3SUM-hard，所以你不太可能比 Theta(n^2) 做得更好。如果我没理解错的话，你现在的算法是O(n^2 log n)，没有留下很大的改进空间。
据我了解，对于给定的 a/b 组合，您不必遍历 L2 的每个元素。 L2 升序排列。然后假设您从 L1 中选择 a/b 的第一个组合。对于 c，您可以选择 L2 中间的元素，即索引 3500 处的元素并乘以 a/b。如果答案小于 M，您可以选择更高索引处的元素，例如 7000*3/4，即 5250。如果答案仍然更少，则继续更高。相反，如果 (a/b)*c 超过 M，则选择一个较低的索引。您可以收敛到特定 a/b 组合的 c 的最大值。
P.S。不用说，在对 L1 和 L2 进行排序后，您可以添加一个 if 语句来消除 L1 或 L2 中的那些元素，这些元素分别对于 L2 或 L1 的任何值总是超过 M。
升序排列 L1。假设|L1| = n。这是 O(n log n)。
对于 L2 中的每个元素（等式中的 'c'），执行以下操作（因此 O(1) 次，因为 L2 是固定的）。
1. For the first element in L1 (which we'll treat as the 'a' in the equation), use binary search on L1 to find a second element (the 'b') s.t. (b/a)*c is maximized but still <=M.
2. Now, we'll move on to the next element in L1. Note that we're increasing the denominator, so the numerator will either stay the same or increase. We'll just iterate rather than using binary search.
3. repeat step 2.
在第 2 步和第 3 步中，我们会跟踪迄今为止为 a、b 和 c 找到的最佳值。
运行 时间：O(n log n) 进行排序，然后在第 2 步中，我们只从每个值递增一次分子或分母，所以这是 O(n) + O(n) = O(n).
这利用了 L2 的固定优势。如果 |L2|=m 且 m 不固定，则需要 O(n log n) + O(m*n)