一个循环？蟒蛇

Question

所以我写了这个函数给出了可能的数字,它必须找到构成给定数字的可能数字内的两个数字.但是,我仍在学习Python(一种非常好的语言),所以我只能使用一组有限的函数.

我创建了这个函数:

def sumPair(theList, n):

    theList = charCount(theList) #charCount is a function i made to convert the list into a dictionary
    for i in theList:
        for a,b in theList.iteritems():
            print a,b
            if a + i == n:
                if theList[b] > 1:
                    return [i, b]
                if a != i:
                    return [i, b]
        return "[]"
print sumPair([6,3,6,8,3,2,8,3,2], 11)   

就像我说的,它找到了两个加起来给定数字的数字.charCount是我写的一个函数,它将数组添加到字典中.

在这个程序中,我确保值大于1,以防添加的数字相同.有时,如果它检查10的总和,你给它一个5的数字,它只会将5添加到自身并返回10.这就是为什么它if theList[b] > 1: 在那里.

为什么我在这里？我的导师对两个循环不满意.我花了5个小时进行故障排除,无处可去.我需要将此程序转换为单循环程序.

我整天都花在这上面,我不是想让你做我的作业,我真的被困住了,我需要你的帮助.我听说我应该检查一下是否有钥匙才能完成.

Answer 1

教师可能不满意你的算法需要的时间比它要长.试试这个:

for each element x in theList
  if there exists an element y in theList such that x+y = n, you have a match

你需要快速进行"if exists"测试,这就是你使用字典的方法.一个循环将构建此字典,第二个将搜索.这将花费线性时间与您的O(n ^ 2)时间.

你对自己的5个匹配点是一个很好的观点.您想使用称为multiset或bag的数据结构.阅读它,然后以这种方式实现您的代码:

for each element x in theList
  if there exists an element y in theList such that x+y == n:
    if x != y or (x == y and x occurs more than once):
      you have a match

祝好运.

编辑因为有这么多次优的解决方案,这里是简单的线性解决方案(它是线性的,因为列表中有2个循环,但是循环一个接一个地出现.所以,2*n次迭代,O(n).非常快.

#!/usr/bin/python2.6

from collections import defaultdict

def sum_list(l, n):
  count = defaultdict(lambda: 0)

  for x in l:      # O(n)
    count[x] += 1  # This can be done in constant time O(1)

  for x in l:      # O(n)
    y = n - x
    if count[y] > 0 and (x != y or count[y] > 1): # O(1)
      return x, y