所以假设列表是 [2,5,14,18,44],我想知道的是 60 以下的两个数字的最大组合是什么。所以正确答案应该是 (14,44)
现在我正在计算每一种可能的组合,然后才能得到结果。效率低得可怕
假设列表按照示例中给出的方式排序,前提是您可以从列表的任一侧使用双指针方法以获得比您当前拥有的
O(n)
更有效的O(n^2)
解决方案:
from typing import Optional
def find_biggest_combination(numbers: list[int],
threshold: int) -> Optional[tuple[int, int]]:
"""
Finds the biggest combination of two numbers under a certain threshold
from a sorted list of numbers.
Args:
numbers: A sorted list of integers to search for a combination.
threshold: An integer representing the upper limit for the sum of
the combination.
Returns:
A tuple of two integers representing the biggest combination found
whose sum is less than the threshold, or None if no such combination
exists.
"""
left, right = 0, len(numbers) - 1
biggest_combination: Optional[tuple[int, int]] = None
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum >= threshold:
right -= 1
else:
if not biggest_combination or current_sum > sum(biggest_combination):
biggest_combination = (numbers[left], numbers[right])
left += 1
return biggest_combination
print(f'{find_biggest_combination([2, 5, 14, 18, 44], 60) = }')
输出:
find_biggest_combination([2, 5, 14, 18, 44], 60) = (14, 44)
这是一种基于从(已排序)列表的两端迭代的可能方法:
def best_pair(nums: list[int], threshold: int) -> tuple[int, int]:
"""Return the pair of nums whose sum is closest to threshold
without meeting or exceeding it."""
nums = sorted(nums)
best = nums[0], nums[1]
if sum(best) >= threshold:
raise ValueError(f'No pair exists under {threshold}.')
j = len(nums) - 1
for i in range(len(nums) - 1):
while nums[i] + nums[j] >= threshold:
j -= 1
if j <= i:
break
if nums[i] + nums[j] > sum(best):
best = nums[i], nums[j]
return best
assert best_pair([2, 4, 14, 18, 44], 60) == (14, 44)
对于列表中的任何给定数字,都有一个特定的其他数字构成最佳可能对。如果您按从小到大 (
i
) 的顺序遍历列表,则这些数字 (j
) 的最佳配对将始终减少。您需要做的就是将 j
减少到足以防止它“破坏”它与任何给定的 i
形成的对。一旦j <= i
你就不能再形成任何有效的对了,你就完了。
这大大减少了您需要考虑的可能性的数量;因为每次迭代只在列表的一个方向上进行,所以整个事情最终变成了 O(n)。
请注意,仅当列表尚未排序时调用
sorted()
是 O(n log n);对于已经排序的列表,它是 O(n)。如果您确定列表将 always 排序,您可以跳过它来节省一些时间,但它不会改变 big-O 运行时。