5

私は今日これを尋ねられました.答えは非常に簡単であることはわかっていますが、彼は最後までひねりを加えてくれました.

質問

ArrayListに格納されている偶数を削除するプログラムを作成して1 - 100ください。

すごいって言っただけ

ほら、これが私がそれを実装した方法です。

ArrayList source = new ArrayList(100);
for (int i = 1; i < 100; i++)
{
    source.Add(i);
}


for (int i = 0; i < source.Count; i++)
{
    if (Convert.ToInt32(source[i]) % 2 ==0)
    {
        source.RemoveAt(i);
    }
}

//source contains only Odd elements

ひねり

彼は私に、この方程式の計算の複雑さは何かと尋ねました。私はちょうどそうして、これはN（入力）に正比例する線形であると言いました。

彼は言った：うーん..つまり、入力サイズが大きくなったときに結果を得るためにもっと長く待つ必要があるということですか？Yes sirr you are

私のためにそれを調整してください、Log(N)彼が言ったことができる限り試してみてください。私はこの部分で惨めに失敗しました。

  • したがって、これを行うための正しいロジック、答え、またはアルゴリズムを求めてここに来てください。

注:彼は、Linq や余分なベルやホイッスルを必要としませんでした。それを行うための単純なループまたはその他のロジック

4

7 に答える 7

5

配列での削除は O(N) であり、項目ごとに呼び出される可能性があるため、複雑さは実際には O(N^2) であるとあえて言います。

したがって、配列（リスト）のトラバーサルにはO（N）があり、各削除にはO（N）=> O（N）* O（N）があります。

よくわからないので、その理由を説明します。各ステップで、アイテムの削除が行われる場合があります (すべてのアイテムを削除する必要があるという最悪のケースを想定しています)。配列では、削除はシフトによって行われます。したがって、最初の項目を削除するには、次の N-1 個の項目をすべて左に 1 桁シフトする必要があります。

1 2 3 4 5 6...
<---
2 3 4 5 6...

さて、各反復でシフトする必要があるので、シフトを行っていN-1 + N-2 + ... + 1 + 0ます。これにより、(N) * (N-1) / 2(算術級数) の結果が得られ、O(N^2) の最終的な複雑さが得られます。

于 2012-05-26T14:51:12.280 に答える
4

次のように考えてみましょう。

実行している削除アクションの数は、強制的に、配列の長さの半分です (要素が配列に格納されている場合)。したがって、複雑さは少なくとも O(N) です。

あなたが受けた質問から、あなたの教授は、数値を格納するさまざまな方法についてあなたに推論してほしいと思っていたと思います。

通常、ログが複雑な場合は、グラフやツリーなどのさまざまな構造で作業しています。

対数的複雑さを持つと考えることができる唯一の方法は、数値をツリーに格納することです (順序付けされたツリー、b ツリー...これについて詳しく説明します)、実際には試験の制約から外れています (数値を並べ替える配列）。

それはあなたにとって理にかなっていますか？

于 2012-05-26T15:11:53.053 に答える
2

現在の読み取り位置と現在の書き込み位置の2つのインデックスを保持すると、パフォーマンスが大幅に向上します。

int read = 0
int write = 0;

アイデアは、readが配列の各メンバーを順番に見るというものです。writeは、リストの現在の終わりを追跡します。削除したいメンバーが見つかると、読み取りを進めますが、書き込みはしません。

for (int read = 0; read < source.Count; read++) {
  if (source[read] % 2 != 0) {
    source[write] = source[read];
    write += 1;
  }
}

次に、最後に、新しい長さが`write'の現在の値であることをArrayListに通知します。

これにより、元のO（n ^ 2）からO（n）に移動します。

（注：これはテストしていません）

于 2012-05-26T15:20:36.427 に答える
1

本当に ArrayList を使用する必要があり、エントリを積極的に削除する必要がある場合 (最初にエントリを追加しない場合)

i + 1 ではインクリメントしませんが、i + 2 を使用すると、奇数かどうかを確認する必要がなくなります。

for (int i = source.Count - 1 ; i > 0; i = i i 2)
{
   source.RemoveAt(i);
}

編集source：これは、1〜100のエントリが順番に含まれている場合にのみ機能することを知っています。

于 2012-05-26T14:55:31.807 に答える
1

無制限の並列スレッドを利用できる場合は可能です。

n要素を持つ配列があるとします。要素ごとに 1 つのスレッドを割り当てます。すべてのスレッドが完全に同期して動作すると仮定します。

  1. 各スレッドは、その要素が偶数か奇数かを決定します。（時間O(1)。）
  2. 配列内でそれより下にある奇数要素の数を決定します。（時間O(log(n))。）
    1. 同じインデックスで偶数か奇数かに応じて、2 番目の配列で 0 または 1 をマークします。したがって、それぞれがそのスポットでのオッズの数です。
    2. 指数が奇数の場合は、前の数値を追加します。現在、各エントリは、現在のブロックのオッズのカウントであり、最大 2 です。
    3. インデックス mod 4 が 2 の場合は、下のインデックスに値を追加します。3 の場合は、下の答えの 2 つのインデックスを追加します。これで、各エントリは、現在のブロックの 4 までのオッズのカウントになります。
    4. このパターンを2**i(上半分にいる場合は、下半分のカウントを追加します)回のブロックで続けます。この配列の各エントリは、以下のオッズのカウントです。log2(n)
  3. 各 CPU は、その値を正しいスロットに挿入します。
  4. 配列を適切なサイズに切り捨てます。

このようなものがあなたの友人が考えている答えであると確信しています.

于 2012-05-26T18:31:41.103 に答える
1

データ構造を変更したり、項目が ArrayList 内に格納される方法を想定したりしなければ、すべてのメンバーのパリティ チェックを回避する方法がわかりません (したがって、少なくともO(n)複雑になります)。おそらく、面接担当者は単に、それは不可能だとあなたに伝えたかったのでしょう。

于 2012-05-26T15:03:13.863 に答える
1

指定されたソリューションの問題は、最初から開始されるため、アイテムが削除されるたびにリスト全体をシフトする必要があることです。

Initial List:       1, 2, 3, 4, 5, ..., 98, 99
                         /  /  /  ///  /
After 1st removal:  1, 3, 4, 5, ..., 98, 99, <empty>
                            /  ///  /   /
After 2nd removal:  1, 3, 5, ..., 98, 99, <empty>, <empty>

スラッシュを使用して、各削除後にリストがどのように変化するかを示しました。

削除の順序を逆にするだけで、複雑さを軽減できます (そして、コメントで言及したバグを排除できます) 。

for (int i = source.Count-1; i >= 0; --i)  {
  if (Convert.ToInt32(source[i]) % 2 == 0) {
    // No need to re-check the same element during the next iteration.
    source.RemoveAt(--i);
  }
}
于 2012-05-26T15:14:05.223 に答える