3

ここに、配列内の一意の整数ペアの数を計算する関数があります。合計は偶数です。現在、ネストされたループを使用してこれをコーディングしましたが、ネストされたループは時間の複雑さをもたらすため、これは非効率的ですO(N²)。

この例でAは、 は配列PをQ表し、整数のペアを表します。そうしないと、一意でない整数のペアが生成されますQ(ここで、P と Q は配列内の同じ値を指すことができます)。P

public int GetEvenSumCount(int[] A)
{
    // result storage
    int result = 0;

    // loop through each array element to get P
    for (int P = 0; P < A.Length; P++)
    {
        // loop through each array element to get Q
        for (int Q = P + 1; Q < A.Length; Q++)
        {
            // calculate whether A[P] + A[Q] is even.
            if ((A[P] + A[Q]) % 2 == 0)
            {
                result++;
            }
        }
    }
    return result;
}

これをリファクタリングして、最悪の場合の時間の複雑さを改善する必要がありますがO(N)、どこから始めればよいかわかりません! これには、ネストされたループではなく、1 つのループのみを使用する必要があることはわかっていますが、この点でどのように合計A[P]するかはわかりません。A[Q]

4

7 に答える 7

5

次の 2 つの方法で偶数の合計を取得できます。

  1. 次のように、2 つの偶数値を追加します。2 + 4 = 6
  2. 次のように、2 つの奇数値を追加します。1 + 3 = 4

逆に、奇数に偶数を足すと常に奇数になります。1 + 2 = 3

したがって、取得できる偶数の合計数は次のとおりです。

  1. 偶数値のペアの数
  2. さらに、奇数値のペアの数

nアイテムのコレクションにあるペアの数は次のとおりです。

N = n * (n-1) / 2

完全なコード:

static bool IsEven(int i)
{
    return i % 2 == 0;
}

static bool IsOdd(int i)
{
    return i % 2 != 0;
}

static int GetPairCount(int n)
{
    return n * (n- 1) / 2;
}

public static int GetEvenSumCount(int[] A)
{
    int evensCount = A.Count(IsEven);
    int oddCount = A.Count(IsOdd);

    return GetPairCount(evensCount) + GetPairCount(oddCount);
}

ご覧のとおり、ネストされたループはなく、実際に合計を計算する必要はありません。

この実装の複雑さは O(N) です。

于 2013-10-12T08:42:00.753 に答える
2

2 つの整数の和が偶数になるのは、両方が奇数か偶数の場合だけです。

配列をスキャンし、奇数と偶数の数を数えます。これらがN1とN2であるとしましょう。

The number of pairs = (N1 Choose 2) + (N2 Choose 2).
                    = N1*(N1-1)/2 + N2*(N2-1)/2
于 2013-10-12T08:40:19.537 に答える
1

約束どおり、解決策を報告します。

static int GetEvenSumCountFast(int[] A)
{
    int[] OddEven = new int[2];
    for (int i = 0; i < A.Length; i++)
        OddEven[A[i] & 1]++;
    return OddEven[0] * (OddEven[0] - 1) / 2 +
        OddEven[1] * (OddEven[1] - 1) / 2;
}

まあ、他の人はすでにそれを解決しましたが、何でも..

別：

static int GetEvenSumCountFast(int[] A)
{
    int odd = 0, even = 0;
    for (int i = 0; i < A.Length; i++)
    {
        odd += A[i] & 1;
        even += ~A[i] & 1;
    }
    return odd * (odd - 1) / 2 +
        even * (even - 1) / 2;
}
于 2013-10-12T08:49:02.360 に答える
1

2 つの偶数の合計は偶数であり、2 つの奇数の合計も偶数であるため (ただし、奇数と偶数の数は奇数です)、最初にそれらを偶数と奇数にグループ化します。

var grouped = A.GroupBy(x => x % 2 == 0);

n が要素の数である各グループの一意のペアの数は次のとおりです。

(n-1) + (n-2) + … + 1 = n * (n-1) / 2

したがって（偶数グループまたは奇数グループに属しているかどうかに関係なく）：

return gouped.Sum(x => {var n = x.Count(); return n * (n-1) / 2; });
于 2013-10-12T08:50:09.393 に答える
0

さて、私は O (n) という解を持っています。すこし。あなたはそれを不正行為と見なすことができます。おそらくそうです。

「int」の範囲は +/- 2^31 に制限されています。

可能な配列サイズは無制限であると想定する必要があります。そうでなければ、O () 表記は意味をなさないからです。配列のサイズが 2^64 要素に制限されている場合、問題は 2^128 演算を使用して一定時間 O (1) で常に解決できます...

したがって、配列に含まれるすべての可能な 2^32 int 値のビットマップを作成します。それには O (n) ステップかかります。すべての重複を削除して、ビットマップから新しい配列を作成します。その配列には、最大で min (n, 2^32) エントリがあります。残りは常に 2^64 操作で実行できます。これは O (1) です。したがって、合計は O (n) ですが、n が約 2^32 の場合、定数係数は非常に大きくなります。

配列に整数ではなくバイトが含まれている場合、これは実際にはかなり高速なアルゴリズムになります。

効率的なアルゴリズムを見つけるのは、ちょっと難しいようです。

于 2014-03-25T00:02:14.617 に答える
0

問題は、一意の偶数の合計を見つけることでした...上記のすべてのソリューションで...奇数と偶数の数を数えるとき、それらは一意性を考慮していません.たとえば、同じ値を持つ2つの偶数がある場合値は 4 で、もう 1 つの偶数は 6 です。値が 10 の偶数の合計が 2 つあり、それらは一意ではありません。

于 2013-10-24T15:04:38.717 に答える