9

この問題のより簡単な、またはより一般的なバージョンは、指定された合計でトリプレットを見つけることです。しかし、これには追加の条件があります。並べ替えられていない配列内のすべてのトリプレットを検索します。

d[i]+d[j]+d[k] <= t;   & d[i]<d[j]<d[k] where i<j<k

これは、問題の最初の部分の解決策です。しかし、誰かがそれを拡張して2番目の条件も含める方法を提案できますか. 私が考えることができる唯一の方法は、ソート中にカスタムデータ構造を実行して、元の要素インデックスと番号を格納することです。そして、含まれているリンクに記載されているアルゴリズムによって返されたすべてのトリプレットのインデックスが適切かどうかを確認します。

4

9 に答える 9

1

O（n ^ 2 log n + k）よりも少し良いことができると思います。

あなたが i の位置にいるとします。i (1...i) までのすべての要素は 1 つの BST に格納され、i (1+1...n) 以降のすべての要素は 2 番目の BST に格納されます。

最初のツリーで、A[j] となるような最小の要素 A[j] を見つけます。

次に、2 番目のツリーで、A[k] < kA[i]-A[j] となる最大の要素 A[k] を見つけます。A[k]<=A[i] の場合は停止します。それ以外の場合は、A[j]、A[i]、A[k] を出力し、2 番目のツリーで k = prev(A[k]) を設定します。A[k]<=A[i] になるまでループします。

このすべての途中で、追加の比較を行います。A[j1] = next(A[j]) とします (つまり、A[j1] はソートされたシーケンスの次の要素です)。ak が条件 A[j1]+A[i]+A[k] <=t にも従う場合、そのような最大の k を書き留めます。次の反復では、二分探索の代わりにこの k を直接使用します。

最初に i=2、firstTree={A[1]}、secondTree = {A[3]..A[n]} から開始します。A[i] を増やすときはいつでも、A[i] を最初のツリーに追加し、2 番目のツリーから A[i+1] を削除します。

全体的な時間の複雑さ: O(n^2+n*log(n)) + O(p) = O(n^2+p) ここで、p は合計結果の数です。

アルゴリズム：

Initialization: firstTree={A[1]}, secondTree = {A[3]..A[n]}

For i = 2:(n-1) do:
    j = getFirst(firstTree)
    firstIter = true;
    while(true)
        if A[j]>=A[i] or A[j]+A[i]>t break
        if firstIter:
            k = binSearch(secondTree, t - A[i] -A[j])
            firstIter=false
        else
            if bestk<0:
                break;
            k = bestk
        bestk = -1
        jnext = nextElement(firstTree, A[j]);
        while (A[k]>A[i]):
            print (A[j], A[i], A[k])
            if bestk<0 and A[i]+A[jnext]+A[k] < t:
                bestk = k;
            k = prevElement(secondTree, A[k])
    Add(firstTree, A[i])
    Remove(secondTree, A[i+1])

binSearch は i ごとに 1 回だけ呼び出され、1 つの i に対して nextElement はツリーを 1 回だけ通過することに注意してください (複雑さ O(n))。内側の while ループは 1 回だけ呼び出されます。したがって、全体的な複雑さは O(n^2 + nlogn + p) で、p は出力の数です。

編集: 成果のない j (つまり、j の解がない) が見つかった場合は停止します。このコストは O(p) 自体に組み込まれていると思います。したがって、最終的な複雑さは O(nlogn + p) です。申し訳ありませんが、詳細な証明を提供する時間がありません。

于 2015-02-03T07:31:08.643 に答える
0

この場合、n^2*logn を達成できると思います。

私たちがしなければならないことは、最初にクイックソートを使用して番号をソートすることです。これにより、余分なループが回避され、デフォルトで i < j < k になります。

私のロジックは d[i] + d[j] + d[k] <= t なので、 d[k] <= t - d[i] -d[j] なので、最初のループは 1 から n まで実行され、2 回目は実行されますi + 1 から n まで、3 番目は (t - d[i] -d[j]) の二分探索を行い、重複を避けるために d[i] < d[j] < d[k] を比較します。したがって、これを行うことで、合計を見つけるために nlogn(sorting) + (n^2*logn) の複雑さを得ることができます。

だから私の呼び出しは：

    Arrays.sort(d);
    for (int i = 0; i < d.length; i++) {
        for (int j = i + 1; j < d.length; j++) {
            int firstNumber = d[i];
            int secondNumber = d[j];
            int temp = t - firstNumber - secondNumber;
            if ((firstNumber < secondNumber) && (secondNumber < temp))  {
                int index = Arrays.binarySearch(d, temp);
                    if (index >= 0) {
                    ......
                    }
                }
            }
        }
    }
于 2015-05-26T09:48:46.707 に答える
-1

i と j を修正すると、配列内で より小さいか等しい数値を見つける必要がありますt - d[i] - d[j]。すべての要素がそのインデックスも格納する配列の 2 番目のバージョンを格納します。この配列を昇順に並べ替えます。

ここで、 (これはネストされた 2 つの for ループにすぎません) のすべてのペアi, jに対して、i < jバイナリ検索を行いt - d[i] - d[j]ます。そのような数値が存在する場合は、左からこの数値までのすべての数値を調べ、それらのインデックスが j より大きいことを確認し、そうであれば出力に追加します。複雑さはO(n*n*lg n + k)、k が条件を満たす出力の数である場合です。

編集：OPの最初の投稿は=、彼がに変更されました<=。答えを更新しました。

于 2015-01-21T20:13:35.823 に答える
-1

キューブの半分が適格でない条件付きで、i<j<k 不要なものを削除できます

for (int k = 0; k < N, k++) 
{
    for (int j = 0; j < k, k++) 
    {       
                if (d[j] < d[k]) continue;
        for (int i = 0; i < j, i++) 
        {
            if (d[k] < d[j]) continue;
            if (d[i]+d[j]+d[k] <= t) 
            {
                 //valid result
            }
        }
    }
}
于 2015-02-03T03:27:31.663 に答える