4

数値が与えられると、合計がその数値に等しい、与えられた配列内のすべての可能なインデックスペアを見つける必要があります。私は現在、次のアルゴリズムを使用しています。

def myfunc(array,num):
    dic = {}
    for x in xrange(len(array)):  # if 6 is the current key,
        if dic.has_key(num-array[x]):  #look at whether num-x is there in dic
            for y in dic[num-array[x]]: #if yes, print all key-pair values
                print (x,y),
        if dic.has_key(array[x]):  #check whether the current keyed value exists
            dic[array[x]].append(x)  #if so, append the index to the list of indexes for that keyed value
        else:
            dic[array[x]] = [x]  #else create a new array

これはO(N)間に合うでしょうか？そうでない場合は、それを実現するために何をすべきですか？O(N)そして、いずれにせよ、補助的なデータ構造を使用せずに時間内に実行することは可能ですか？

4

3 に答える 3

6

これはO（N）時間で実行されますか？

はいといいえ。複雑さは、実際O(N + M)にMは出力サイズがどこにあるかです。
残念ながら、出力サイズはO(N^2)最悪の場合、たとえば配列[3,3,3,3,3,...,3]であり、number == 6結果として2次数の要素を生成する必要があります。

ただし、漸近的に言えば、入力サイズと出力サイズが線形であるため、これよりも優れた方法はありません。

于 2012-09-23T08:00:23.477 に答える
3

配列参照を使用して実際にO（N）時間で実行される非常に単純なソリューション。すべての出力ペアを列挙する場合は、もちろん（amitノートとして）最悪の場合はO（N ^ 2）を取る必要があります。

from collections import defaultdict
def findpairs(arr, target):
    flip = defaultdict(list)
    for i, j in enumerate(arr):
        flip[j].append(i)
    for i, j in enumerate(arr):
        if target-j in flip:
            yield i, flip[target-j]

(i,i)すべての出力値を取得する（および回答を除外する）後処理：

def allpairs(arr, target):
    for i, js in findpairs(arr, target):
        for j in js:
            if i < j: yield (i, j)
于 2012-09-23T08:04:38.440 に答える
1

これは役立つかもしれません-与えられた整数kで割り切れるペアを見つけるために必要な最適なアルゴリズム

（わずかな変更を加えると、指定された数で割り切れるすべてのペアが表示されますが、必ずしも指定された数と同じである必要はありません）

于 2012-09-23T09:06:02.053 に答える