我正在尝试解决一个问题,该问题需要我在列表中找到对的总和。对索引必须是唯一的,即任何单个索引都不应成对出现。例如 -
my_list = [1,1,2,3,4,5]
sum_greater_than_or_equal_to = 5
在这里,我有一个排序列表,想找到总和大于或等于5的所有对。因此,我可以通过进行另一个循环来查找对来解决O(n ^ 2)中的这个问题。在多对中不使用索引的对是-
output = [(1,4),(1,5),(2,3)]
还有另一种更有效的方法吗?无需创建两个循环?
编辑-人们提到包含值的答案-[(2,4),(2,5),(3,4),(3,5),(4,5)]
但我希望,如果列表的索引已经成对使用,就不能再次使用。
以下代码将生成此类对的一种可能组合:
my_list = [1,1,2,3,4,5]
def find_pairs(arr, limit):
arr = sorted(arr)
res = []
start = 0
end = len(arr) - 1
while start < end:
if arr[start] + arr[end] >= limit:
res.append((arr[start], arr[end]))
end -= 1
start += 1
return res
print find_pairs(my_list, 5) # [(1, 5), (1, 4), (2, 3)]
对于给定的测试集,解决方案[(3,4), (2,5)]
也将是有效的答案。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句