8

我有两个由数字（整数）组成的列表；两者都有 200 万个独特的元素。

我想从列表 1 中找到数字 a，从列表 2 中找到数字 b，即 -

1)a*b should be maximized.
2)a*b has to be smaller than certain limit.

这是我想出的：

maxpq = 0
nums = sorted(nums, reverse=True)
nums2 = sorted(nums2, reverse=True)
for p in nums:
    n = p*dropwhile(lambda q: p*q>sqr, nums2).next()
    if n>maxpq:
        maxpq=n
print maxpq

有什么建议么？编辑：我的方法太慢了。这将需要超过一天的时间。

4

3 回答 3

4

这是一个线性时间解决方案（排序后）：

def maximize(a, b, lim):
    a.sort(reverse=True)
    b.sort()
    found = False
    best = 0
    j = 0
    for i in xrange(len(a)):
        while j < len(b) and a[i] * b[j] < lim:
            found = True
            if a[i]*b[j] > best:
                best, n1, n2 = a[i] * b[j], a[i], b[j]
            j += 1
    return found and (best, n1, n2)

简单的说：

  • 从每个列表的最高和最低开始
  • 当他们的产品低于目标时，推进小项目
  • 一旦产品变得比你的目标大，推进大项目，直到它再次低于你的目标

这样，您可以保证每个列表只浏览一次。False如果找不到足够小的东西，它将返回，否则它将返回产品和生产它的对。

样本输出：

a = [2, 5, 4, 3, 6]
b = [8, 1, 5, 4]
maximize(a, b, 2)   # False
maximize(a, b, 3)   # (2, 2, 1)
maximize(a, b, 10)  # (8, 2, 4)
maximize(a, b, 100) # (48, 6, 8)
于 2012-11-17T03:44:28.187 回答
1

感谢大家的建议和想法。我终于想出了有用的解决方案。inspectorG4dget 先生对此有所了解。

它使用bisectpython 标准库中的模块。

编辑： bisect 模块进行二进制搜索，以便在排序列表中找到值的插入位置。因此，与我之前的解决方案不同，它减少了比较次数。

http://www.sparknotes.com/cs/searching/binarysearch/section1.rhtml

import bisect

def bisect_find(num1, num2, limit):
    num1.sort()    
    max_ab = 0

    for a in num2:
        complement = limit / float(a)
        b = num1[bisect.bisect(num1, complement)-1]

        if limit > a*b > max_ab:
            max_ab=b*a

    return max_ab
于 2012-11-17T03:40:42.870 回答
0

这可能会更快。

def doer(L1, L2, ceil):
    max_c = ceil - 1
    L1.sort(reverse=True)
    L2.sort(reverse=True)
    big_a = big_b = big_c = 0

    for a in L1:
        for b in L2:
            c = a * b
            if c == max_c:
                return a, b
            elif max_c > c > big_c:
                big_a = a
                big_b = b
                big_c = c

    return big_a, big_b


print doer([1, 3, 5, 10], [8, 7, 3, 6], 60)

请注意，它会就地对列表进行排序；这更快，但可能适合也可能不适合您的场景。

于 2012-11-17T03:12:05.903 回答