9

今日のインタビューでこんな質問をされました。私は解決策を試しましたが、これを解決するためのより良い方法があるかどうか知りたいです:

質問: arraylist の各要素の値がインデックスと同じになるように、500,000 要素の arraylist があります。例: list.get(0) = 0; list.get(1) = 1 ...など。しかし、この順序と同期していない要素は 1 つだけです [つまり、list.get(i) != i]。その要素をどのように見つけますか。

私の答え: list.get(i) と i を比較するたびに、各スレッドが arraylist の特定のスプライスを処理する複数のスレッドを使用して、リストを反復処理します。要素が見つかったら、ブール変数を設定して、要素が見つかったことを他のスレッドに示します。

リストを繰り返し処理せずにこの問題を解決する方法はありますか? それとももっと良い方法ですか？

4

6 に答える 6

13

最悪の場合、各要素を調べる必要があるため、O(n)時間の複雑さを改善することはできません。

これを念頭に置いて、最適なアルゴリズムは配列リストを最初から最後までスキャンすることです。このようにして、利用可能なメモリ帯域幅を最大限に活用しています。

スレッド化がどのように、またはなぜこの図に入ったのかは、私には完全には明らかではありません。それは場違いのようです。それは質問の一部でしたか？

于 2012-04-26T14:09:48.017 に答える
6

答えは: 1 回の繰り返しです。原因の並行性についてのあなたの言及は、彼らが釣りをしているものです。

実際、Java 8以降、並列かどうかの解決策は簡単です。私は、最も持ってきたと思います：

OptionalInt foundInt = IntStream.range(0, list.size())
    .parallelStream()
    .filter(i -> i != list.get(i))
    .findAny();
于 2016-08-11T14:49:45.393 に答える
2

あなたはより良くすることはできませんO(n)。

第二に、これらの問題でスレッドやマルチスレッドについて話すのは悪い考えだと思います。それらはまったく興味がありません。最終的に、とにかく定数が削除される O(whatever) のランタイムがあります。

おそらく、インタビュアーは、インデックス 0 から n-1 を持つ 0 から n-1 までの要素を持つソートされた配列を意味していたのでしょう。次に、1 つの要素を別の位置に移動します。しかし、それは残りのすべての要素が異なるインデックスを持つことを意味します! このシナリオでは、バイナリ検索を使用して検索を改善できます。

次に、 で要素を取得できますO(log n)。途中から始めて、インデックスが要素と等しいかどうかを確認します。等しい場合は、半分の上部で同じことを行い、そうでない場合は他の部分を使用します.

于 2012-04-26T14:11:07.170 に答える
0 
1. iterate through the list 
2. check for the condition in the elements
3. when that only element found break out the loop...

スレッドがアリーナに入るとは思わない...

于 2012-04-26T14:23:38.387 に答える
0

@aixの回答に加えて、ループごとに2つのチェックを行うのはどうですか:

for (int i = 0; i < list.size / 2; i++)
{
  if (i != list.get(i))
  {
    return i;
  }
  else if (list.size - i != list.get(list.size - i)
  {
    return list.size - i;
  }
}
于 2012-04-26T14:19:42.163 に答える