8

数字（整数）で構成された2つのリストがあります。どちらも 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

助言がありますか？編集：私の方法は遅すぎます。1日以上かかります。

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)

簡単に言えば：

  • 各リストの最高値と最低値から開始
  • 自社製品が目標を下回っている間、小物を進める
  • 製品が目標よりも大きくなったら、再び下回るまで大きなアイテムを進めます

このようにして、各リストを 1 回だけ確認することが保証されます。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 に答える