12

フロートの並べ替えられた配列を入力として指定すると、 for each(i,j)などのペアの総数を見つける必要があります。O（n ^ 2）アルゴリズムを提供する他のループ内のループを使用して、単純な解決策をすでに知っていますが、より最適な解決策があるかどうか疑問に思っていました。A[i]*A[j]>=A[i]+A[j]i < j

4

5 に答える 5

8

これがO(n)アルゴリズムです。

を見てみましょうA * B >= A + B。

  • の場合A, B <= 0、常に true です。

  • の場合A, B >= 2、常に true です。

  • A >= 1, B <= 1(または) の場合B >= 1, A <= 1、常に false です。

  • 0 < A < 1, B < 0(または) の場合0 < B < 1, A < 0、true または false のいずれかになります。

  • 1 < A < 2, B > 0(または) の場合1 < B < 2, A > 0、true または false のいずれかになります。

これは、 Wolfram AlphaとGeobitsの厚意による視覚化です。

さて、アルゴリズムに。

* 1 つの数値が 0 と 1 または 1 と 2 の間にあるペアを見つけるには、3SUM の問題と同様のことを行います。

※ここでの「Pick 2」は組み合わせのことです。

  • 両方が負であるすべてのペアを数えます

    二分探索を実行して、最初の正の (> 0) 数値 - のインデックスを見つけますO(log n)。

    インデックスがあるので、負/ゼロの数がいくつあるかがわかります。そのうちの 2 つを選択するだけでよいので、それがamountNonPositive * (amountNonPositive-1) / 2-O(1)です。

  • 1 が 0 と 1 の間にあるすべてのペアを見つける

    二分探索を実行して、最後の数値 < 1 - のインデックスを見つけますO(log n)。

    そのインデックスから右インデックス、左端の要素を左インデックスとして開始します。

    右のインデックス <= 0 になるまでこれを繰り返します: (runs in O(n))

    • 積が合計よりも小さい間、左のインデックスを減らします

    • 左のインデックスより大きいすべての要素を数えます

    • 右側のインデックスを減らす

  • 1 が 1 と 2 の間にあるペアをすべて見つけます

    二分探索を実行して、最初の数値 > 1 - のインデックスを見つけますO(log n)。

    そのインデックスから左インデックス、右端の要素を右インデックスとして開始します。

    左のインデックス >= 2 になるまでこれを繰り返します: (runs in O(n))

    • 積が合計よりも大きい間、右のインデックスを減らします

    • 右のインデックスより大きいすべての要素を数えます

    • 左のインデックスを増やす

  • 両方の数が 2 以上のすべてのペアを数えます

    最後のステップが終わると、最初のインデックス >= 2 になります。

    ここから、残りのすべての数字から 2 つを選択する必要がある
    ので、これもまたamountGreaterEqual2 * (amountGreaterEqual2-1) / 2-O(1)です。

于 2013-11-07T16:39:46.920 に答える
1

二分探索、O(n log n) は次のとおりです。

の各数値にはブレーク ポイントがありA*B = A+Bます。これを に減らすことができますB = A / (A - 1)。片側または反対側のすべての数字が収まります。負の数などがあっても構いません。

  • の場合A < 1、すべての数値<= Bが適合します。

  • の場合A > 1、すべての数値>= Bが適合します。

  • の場合A == 1、一致はありません (ゼロ除算)。

( Wolfram Alpha リンク)

したがって、いくつかの擬似コード:

loop through i
    a = A[i]
    if(a == 1)
        continue
    if(a >= 2)
        count += A.length - i 
        continue

    j = binsearch(a / (a-1))

    if(j <= i)
        continue

    if(a < 1)
        count += j-i
    if(a > 1)
        count += A.length - j
于 2013-11-07T17:01:07.237 に答える
1

O(n)配列の要素が正の場合の問題を解決するアルゴリズムを次に示します。

要素が正の場合、次のように言えます。

  • If A[i]*A[j] >= A[i]+A[j]when j>ithen A[k]*A[j] >= A[k]+A[j]for any kthat k>iis met (配列がソートされているため)。

  • If A[i]*A[j] < A[i]+A[j]when j>ithen A[i]*A[k] < A[i]+A[k]for any kthatを満たすk<j.

(これらの事実は、両方の数値が分数の場合には成立しませんが、いずれにせよ条件は満たされません)

したがって、次のアルゴリズムを実行できます。

int findNumOfPairs(float A[])
{    
    start = 0;
    end = A.length - 1;
    numOfPairs = 0;

    while (start != end)
    {
        if (A[start]*A[end] >= A[start]+A[end])
        {
            numOfPairs += end - start;
            end--;
        }
        else
        {
            start++;
        }
    }

    return numOfPairs;
}
于 2013-11-07T16:16:00.543 に答える
-1

最初に 1.0 未満のすべての float を除外するのはどうですか。任意の数が 1 未満の数の倍数であるため、i < j ごとに x*0.3=A[i]+A[j] であるため、配列の数だけをカウントする必要があります。ペア（i、j）の数を計算するには、順列と組み合わせに関する式を使用して計算できます。式は n(n-1)/2 である必要があります。

于 2013-11-07T16:21:51.643 に答える