3

就職の面接で質問されたのですが、正解がわかりませんでした…。

質問は次のとおりです。

1 から 100 までの 10 000 000 個の int の配列がある場合、これらの int のペアの合計が 150 以下になる数を (効率的に) 決定します。

ループ内のループなしでこれを行う方法はわかりませんが、あまり効率的ではありません。

誰か私にいくつかの指針を教えてください。

4

3 に答える 3

7

1 つの方法は、100 要素の小さな配列を作成することです。10,000,000 個の要素をループして、それぞれの数を数えます。カウンターを 100 要素配列に格納します。

    // create an array counter of 101 elements and set every element to 0
    for (int i = 0; i < 10000000; i++) {
          counter[input[i]]++;
    }

次に、1 から 100 までの 2 番目のループ j を実行します。その中に、1 から min(150-j,j) までのループ k があります。k!=j の場合、counter[j]*counter[k] を追加します。k=j の場合、(counter[j]-1)*counter[j] を追加します。

合計はあなたの結果です。

合計実行時間は、10,000,000 + 100*100 = 10,010,000 (実際にはこれよりも小さい) で制限されます。

これは、100,000,000,000,000 である (10,000,000)^2 よりもはるかに高速です。

もちろん、メモリ内の 101 int スペースを放棄する必要があります。

完了したらカウンターを削除します。

また、(以下の説明で指摘されているように) これは順序が重要であると想定していることにも注意してください。順序が重要でない場合は、結果を 2 で割ります。

于 2013-01-10T07:16:35.537 に答える
0

まず、配列を並べ替えます。次に、ソートされた配列のシングルパスを開始します。そのセルで単一の値nを取得し、まだ許可されている対応する最小値を見つけます（たとえば、15の場合は135です）。これで、配列内にこの値のインデックスが見つかります。これがnのペアの数です。これらすべてを合計すると、（私の心が正しく機能している場合）各ペアを2回カウントしているので、合計を2で割ると、正しい数になります。

解は、O（n ^ 2）である些細なものと比較してO（n log n）である必要があります

于 2013-01-10T09:30:00.050 に答える
0

この種の質問には、常に数学的洞察と効率的なプログラミングの組み合わせが必要です。彼らはブルートフォースを望んでいません。

最初の洞察

数字は、他のグループとどのようにペアになるかに従ってグループ化できます。

それらを入れる：

1 - 50 | 51 - 75 | 76 - 100
  A    |    B    |    C
  • グループAは何でもペアリングできます。
  • グループはおよび とペアBにすることができますABpossibly C
  • グループはおよび とCペアリングできますが、ペアリングできませんApossibly BC

possiblyもう少し洞察が必要なところです。

第二の洞察

B の各数値について、150 の補数までの数値がいくつあるかを確認する必要62がBありCます88。

の各数値に対して、Cそれまでの集計を合計します。たとえば、76、77、78、...、88 の集計です。これは数学的に部分和として知られています。

標準ライブラリには、partial_sum

vector<int> tallies(25); // this is room for the tallies from C
vector<int> partial_sums(25);

partial_sum(tallies.begin(), tallies.end(), partial_sums.begin());

対称性とは、この合計を 1 つのグループに対してのみ行う必要があることを意味します。

3 番目の (ずっと後の) 洞察

Aグループの合計の計算は、Bを使用して行うこともできpartial_sumます。したがって、 group だけを計算しCて合計を別の方法で追跡するのではなく、1 から 100 までの各数値の合計を保存し、全体に対して partial_sum を作成します。partial_sums[50]は 50 以下の数を返し、partial_sums[75] は 75 以下の数を返し、partial_sums[100] は 1000 万、つまり 100 以下のすべての数になります。

B最後に、との組み合わせを計算できますC。50 と 100、51 と 99、52 と 98 などの合計のすべての倍数を合計したいのですが、50 から 75 までの集計と 100 から 75 までの部分合計を繰り返すことでこれを行うことができます。標準があります。inner_productこれを処理できるライブラリ関数。

これは私にはかなり直線的に見えます。

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 100);

vector<int> tallies(100);
for(int i=0; i < 10000000; ++i) {
    tallies[dis(gen)]++;
}

vector<int> partial_sums(100);
partial_sum(tallies.begin(), tallies.end(), partial_sums.begin());

int A = partial_sums[50];
int AB = partial_sums[75];
int ABC = partial_sums[100]; 
int B = AB - A;
int C = ABC - AB;

int A_match = A * ABC;
int B_match = B * B;
int C_match = inner_product(&tallies[50], &tallies[75],
                            partial_sums.rend(), 0);
于 2013-01-10T10:34:09.563 に答える