10

これは最近インタビューで友人に尋ねられましたが、単純な O(n 3 )以外の解決策はわかりません。

より良いアルゴリズムはありますか？

問題は、合計が指定された合計 S 以下である整数配列内のすべてのトリプレットを見つけることです。

注: パフォーマンスが O(n 2arr[i] + arr[j] + arr[k] = S log n) の SO で他のこのような問題を見たことがありますが、それらはすべて、このようなトリプレットが 1 つ存在するかどうかのみをチェックする場所や場所など、この問題のより簡単なバージョンを解決していました。

私の質問は、そのようなすべてi,j,kを見つけることですarr[]arr[i] + arr[j] + arr[k] <= S

4

5 に答える 5

5

アイデアはありますが、うまくいくかどうかはわかりません。

前処理 (要素の削除 > S) を行い、最初に配列を並べ替えます。

arr[i]次に、とarr[j]whereを拾った後、残りのi < jを二分探索することができます。インデックス をバイナリ検索すると、 と の間にある可能性があります。S - arr[i] - arr[j]array[j+1...n]mkj+1m

これにより、複雑さが軽減される可能性があると思います。どう思いますか？

于 2013-07-18T04:41:12.680 に答える
0

元の回答を以下に残しておきますが、これは実際には O(n) で解決できます。私の新しいソリューションでは、キューを使用してトリプレットを追跡します。トリプレットの数のみを返しますが、それが必要な場合は、リストを作成してトリプレットのリストを簡単に追跡できます。

    class Queue (object):
      def __init__ (self):
        self.queue = []
        self.itemCount = 0

      def enqueue (self, item):
        self.queue.append (item)
        self.itemCount += 1

      def dequeue (self):
        self.itemCount += 1
        return (self.queue.pop(0))


    def findAllTriplets(li,S):
      if len(li) < 3:
        return "Not enough elements for triplets"
      tQ = Queue() # Queue to keep track of data
      tripletNum = 0 # Integer to track number of triplets to be returned
      tripletSum = 0 # Value of sum of consecutive list items for tripletNum evaluation
      for number in li:
        # Add the number to the queue immediately and add it to the current triplet sum
        tQ.enqueue(number)
        tripletSum += number
        # For the first 3 numbers only enqueue and add to the sum
        if tQ.itemCount < 3:
          continue
        # Afterwards, check if the sum of the latest three is less than S
        else:
          if(tripletSum <= S):
            tripletNum += 1
          # Dequeue the oldest element in the queue and subtract it from the tracked triplet sum
          tripletSum -= tQ.dequeue()
      return tripletNum

私は、このアルゴリズムが O(N 2 ) でうまくいくはずだと信じています。ただし、事前に配列をソートする必要があります。

基本的に、最初のインデックス i がゼロで、次のインデックスが j であるすべての可能なトリプレットを見つけるだけです。残りのインデックス (k) を検索して、x (またはあなたの場合は S) 以下のすべての合計を探します。その後、j を 1 増やして、このプロセスを繰り返します。j が配列の最後に到達したら、i が i + 1 であるプロセスを最初からやり直し、i が最後から 2 番目のインデックス値に等しくなるまで続けます (その時点で可能なトリプレットが残っていないため)。

Python コード

def numTriplets(a,x):
   if len(a) < 3:
       return None
   i = 0
   j = 1
   triplets = []
   while True:
      for k in range(j+1,len(a)):
         if a[i] + a[j] + a[k] <= x:
            triplets.append([i,j,k])
      j += 1
      if j == len(a) - 1:
         i += 1
         j = i + 1
      if i == len(a) - 2:
         return triplets
于 2016-12-16T15:21:37.130 に答える
0

これの複雑さは何ですか？

並べ替えられたリスト (昇順) に適用された場合、重複を作成したり、大きすぎる最初の要素をスキャンしたりせずに、f合計が より小さいか等しいトリプレットをs1 つずつリストするだけです。

Haskell コード:

f []     s result = if length result == 3 then [result] else []
f (x:xs) s result
  | length result == 3   = [result]
  | x + sum result > s   = []
  | otherwise            = f xs s (x:result) ++ f xs s result

出力：

*Main> length $ f [1..300] 300 []
731375
(5.09 secs, 402637784 bytes)

*Main> f [1..10] 13 []
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1]
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1]
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2]
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]]
于 2013-07-20T03:58:21.907 に答える
0

これは、O(n 2 ) の複雑さで解決できます。

最初に数字を並べ替える → O(nlog(n))

今、前から始めて、一度に 1 つの番号を修正します。問題は、ソートされた配列内で合計が指定された合計以下である 2 つの数値を見つけることになります。2 つのポインター (開始から 1 つと終了から 1 つ) を使用すると、これは O(n) で解決できます。したがって、全体の複雑さは O(n 2 )です。

于 2016-08-28T06:59:32.880 に答える