0

特定の違いがある数字のリストでペアの数を見つけようとしています。言って、リストで

1 2 3 4 5

このシーケンスには 3 つのペアがあり、差が '2' であるため、数字 '3' を出力したいと思います。ただし、私のコードは非常に遅いです。すべてのペアを二重にカウントするため、答えを得るためにソリューションを 2 で割る必要があります。二重カウントせずにこの同じタスクを達成する方法はありますか? あなたが持っているかもしれない洞察に感謝します。ありがとう！コードは下に印刷されています

    import sys


    def main():
        solutions=0
        pairs=[]
        for i in xrange(len(numbers)):
            for j in xrange(len(numbers)):
                if i!=j:
                    pairs.append([numbers[i], numbers[j]])

        for pair in pairs:
            if abs(pair[0]-pair[1])==k:
                solutions+=1
            else:
                continue
        return solutions/2



    if __name__ == '__main__':
        lines=sys.stdin.readlines()
        n,k=map(int, lines[0].strip().split())
        numbers=map(int, lines[1].strip().split())
        print main()
4

3 に答える 3

3

の各要素についてi、も にあるaかどうかを確認します。~O(1) メンバーシップのテストでは、セットを使用できます。したがって：i-diffa

>>> a = [1,2,3,4,5]
>>> diff = 2
>>> a_set = set(a)
>>> sum(i-diff in a_set for i in a_set)
3

これは O(len(a)) です。

i-diff in a_set[である がとしてbool評価されるという事実を使用したことに注意してください。これは と同等です。]1intsum(1 for i in a_set if i-diff in a_set)

更新: 数値が一意であると想定していることに気づきました。そうでない場合は、大丈夫ですcollections.Counter。代わりに a を使用して、多重度情報を保持できます。

于 2013-01-12T05:56:49.083 に答える
0

配列をソートすると、O(n^2) 検索を行う代わりに、配列をウォークするだけですべてのペアを見つけることができます。二重カウントの理由は、使用したabsため、(1,3) だけでなく (3,1) も検出されるためです。

于 2013-01-12T05:50:55.240 に答える
0

最初に配列をソートし、次にnumリスト内の各番号 ( ) を探す必要がありますnum-2。それを行うための速い方法はbinary search.

したがって、バイナリ検索を使用すると、O(n log(n))解決策が得られます。

于 2013-01-12T05:52:24.977 に答える