5

面接の質問です。0 から N-1 までの要素を含むサイズ N の整数の配列があります。数値が 2 回以上発生する可能性があります。目標は、合計が特定の数 X になるペアを見つけることです。

プライマリ配列の要素数を持つ補助配列を使用して、補助配列に従ってプライマリを再配置し、プライマリがソートされてからペアが検索されるようにしました。

しかし、インタビュアーはスペースの複雑さを一定にしたかったので、配列をソートするように彼に言いましたが、それはnlogn timeの複雑さの解決策です. 彼は O(n) ソリューションを望んでいました。

余分なスペースなしで O(n) でそれを行う方法はありますか?

4

3 に答える 3

6

いいえ、そうは思いません。バケットに割り当てて O(n) のデータを「並べ替える」ことができるように追加のスペースが必要か、O(n) ではないインプレースで並べ替える必要があります。

もちろん、特定の仮定を立てることができれば、常にトリックがあります。たとえば、N < 64K整数が 32 ビット幅の場合、カウント配列に必要なスペースを現在の配列の上に多重化できます。

つまり、配列に値を格納するために下位 16 ビットを使用し、インデックスに一致する値のカウントを格納するだけの配列に上位 16 ビットを使用します。

簡単な例を使用してみましょうN == 8。したがって、配列の長さは 8 要素で、各要素の整数は 8 ビット幅ですが、8 未満です。これは、(最初は) 各要素の上位 4 ビットがゼロであることを意味します。

  0    1    2    3    4    5    6    7    <- index
(0)7 (0)6 (0)2 (0)5 (0)3 (0)3 (0)7 (0)7

カウントを上位 4 ビットに格納する O(n) 調整の擬似コードは次のとおりです。

for idx = 0 to N:
    array[array[idx] % 16] += 16 // add 1 to top four bits

例として、7 を格納する最初のインデックスを考えてみましょう。したがって、その割り当てステートメントはインデックス 7 に 16 を加算し、7 のカウントを増やします。モジュロ演算子は、既に増加した値が下位 4 ビットのみを使用して配列インデックスを指定することを保証するためのものです。

したがって、配列は最終的に次のようになります。

  0    1    2    3    4    5    6    7    <- index
(0)7 (0)6 (1)2 (2)5 (0)3 (1)3 (1)7 (3)7

次に、定数空間に新しい配列があり、使用して値int (array[X] / 16)の数を取得できXます。

しかし、それはかなりよこしまであり、前述のように特定の仮定が必要です。インタビュアーが求めていたのは、そのレベルの悪意かもしれませんし、単に、将来の従業員がコーディングの小林丸をどのように扱っているかを見たいだけかもしれません:-)

カウントを取得したらX、O(N) のままで、合計が所定の になるペアを見つけるのは簡単なことです。基本的なアプローチは、デカルト積を取得することです。たとえば、再びN8 であり、合計が 8 になるペアが必要であるとします。上記の多重化された配列の下半分は無視します (カウントのみに関心があるため、次のようになります。

 0   1   2   3   4   5   6   7    <- index
(0) (0) (1) (2) (0) (1) (1) (3)

基本的に行うことは、配列を 1 つずつ調べて、合計が 8 になる数値のカウントの積を取得することです。

  • 0 の場合は、8 を追加する必要があります (これは存在しません)。
  • 1 の場合、7 を追加する必要があります。カウントの積は 0 x 3 であるため、何も得られません。
  • 2 の場合、6 を追加する必要があります。カウントの積は 1 x 1 であるため、 が 1 回出現し(2,6)ます。
  • 3 の場合、5 を追加する必要があります。カウントの積は 2 x 1 であるため、 が 2 回出現し(3,5)ます。
  • 4の場合はご使用いただけない特殊なケースです。この場合、4 がないので問題ありませんが、1 つある場合、ペアになることはできません。ペアリングしている数字が同じ場合、式は (mそれらがあると仮定して)1 + 2 + 3 + ... + m-1です。ちょっとした数学的な冒険で、それはm(m-1)/2.

それを超えると、左側の値とペアになっていますが、これは既に行っているのでやめます。

だから、あなたが終わったもの

a b c d e f g h <- identifiers
7 6 2 5 3 3 7 7

は：

(2,6) (3,5) (3,5)
(c,b) (e,d) (f,d) <- identifiers

その他の値の合計が 8 になることはありません。

次のプログラムは、この動作を示しています。

#include <stdio.h>

int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 4, 4, 4, 4};
#define SZ (sizeof(arr) / sizeof(*arr))

static void dumpArr (char *desc) {
    int i;
    printf ("%s:\n   Indexes:", desc);
    for (i = 0; i < SZ; i++) printf (" %2d", i);

    printf ("\n   Counts :");
    for (i = 0; i < SZ; i++) printf (" %2d", arr[i] / 100);

    printf ("\n   Values :");
    for (i = 0; i < SZ; i++) printf (" %2d", arr[i] % 100);

    puts ("\n=====\n");
}

上記のビットはデバッグ用です。バケットの並べ替えを行う実際のコードは次のとおりです。

int main (void) {
    int i, j, find, prod;

    dumpArr ("Initial");

    // Sort array in O(1) - bucket sort.

    for (i = 0; i < SZ; i++) {
        arr[arr[i] % 100] += 100;
    }

そして、ペアリングを行うコードで終了します。

    dumpArr ("After bucket sort");

    // Now do pairings.

    find = 8;
    for (i = 0, j = find - i; i <= j; i++, j--) {
        if (i == j) {
            prod = (arr[i]/100) * (arr[i]/100-1) / 2;
            if (prod > 0) {
                printf ("(%d,%d) %d time(s)\n", i, j, prod);
            }
        } else {
            if ((j >= 0) && (j < SZ)) {
                prod = (arr[i]/100) * (arr[j]/100);
                if (prod > 0) {
                    printf ("(%d,%d) %d time(s)\n", i, j, prod);
                }
            }
        }
    }

    return 0;
}

出力は次のとおりです。

Initial:
   Indexes:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
   Counts :  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   Values :  3  1  4  1  5  9  2  6  5  3  5  8  9  4  4  4  4
=====

After bucket sort:
   Indexes:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
   Counts :  0  2  1  2  5  3  1  0  1  2  0  0  0  0  0  0  0
   Values :  3  1  4  1  5  9  2  6  5  3  5  8  9  4  4  4  4
=====

(2,6) 1 time(s)
(3,5) 6 time(s)
(4,4) 10 time(s)

入力数字を調べると、ペアが正しいことがわかります。

于 2013-01-31T08:03:00.877 に答える
1

これは、入力配列を O(N) 時間で「その場で」カウンターのリストに変換することによって行うことができます。もちろん、これは入力配列が不変ではないことを前提としています。各配列要素の未使用ビットに関する追加の仮定は必要ありません。

次の前処理から始めます。各配列の要素を、要素の値によって決定される位置に移動してみてください。この位置にある要素を、その値によって決定される位置にも移動します。まで続ける:

  • 次の要素は、このサイクルが開始された位置から移動されます。
  • 次の要素は、その値に対応する位置に既にあるため、移動できません (この場合、現在の要素をこのサイクルが開始された位置に配置します)。

前処理の後、すべての要素は「適切な」位置に配置されるか、「適切な」位置を「ポイント」します。各要素に未使用のビットがある場合、適切に配置された各要素をカウンターに変換し、それを「1」で初期化し、各「ポインティング」要素が適切なカウンターを増加できるようにすることができます。追加のビットにより、カウンターと値を区別できます。追加のビットなしで同じことを行うことができますが、それほど単純ではないアルゴリズムを使用できます。

k=2配列内の値が 0 または 1 に等しい数を数えます。そのような値がある場合は、それらをゼロにリセットし、位置 0 および/または 1 でカウンターを更新しますk。カウンター）。k = 2, 4, 8, ... に対して次の手順を適用します。

  1. 「適切な」位置にある要素を見つけk .. 2k-1、それらをカウンターに置き換えます。初期値は「1」です。
  2. k .. 2k-1値を持つ位置にある任意の要素について、位置にある2 .. k-1対応するカウンターを更新し2 .. k-1、値をゼロにリセットします。
  3. 0 .. 2k-1値を持つ位置にある任意の要素について、位置にあるk .. 2k-1対応するカウンターを更新しk .. 2k-1、値をゼロにリセットします。

この手順のすべての反復は、一緒に O(N) 時間の複雑さを持ちます。最後に、入力配列はカウンターの配列に完全に変換されます。ここでの唯一の問題は、位置に最大 2 つのカウンター0 .. 2k-1が より大きい値を持つ可能性があることですk-1。ただし、これは、それぞれに 2 つの追加のインデックスを格納し、これらのインデックスで要素を値ではなくカウンターとして処理することで軽減できます。

Xカウンターの配列が生成された後、必要なペアのカウントを取得するために、カウンターのペア (対応するインデックスのペアの合計が になる) を乗算するだけです。

于 2013-01-31T15:52:32.980 に答える
0

文字列の並べ替えは n log n ですが、数値が制限されていると想定できる場合 (合計すると特定の値になる数値にのみ関心があるため、制限がある場合)、基数並べ替えを使用できます。基数ソートには O(kN) 時間がかかります。ここで、「k」はキーの長さです。あなたの場合、それは定数なので、O(N) と言っても過言ではないと思います。

ただし、一般的には、ハッシュなどを使用してこれを解決します

http://41j.com/blog/2012/04/find-items-in-an-array-that-sum-to-15/

もちろん、それは線形時間の解決策ではありません。

于 2015-03-04T20:31:43.827 に答える