0

C＃に関連するインタビューでこれを尋ねられました。2つのアレイがあります-最低から最高に事前にソートされています。これらすべてを組み合わせて3番目の配列に配置する必要があり、並べ替えられた方法で挿入する必要があります（入力時に）。

私が言及した解決策は以下の通りでした：

  1. 議論のためArray 1に、次の要素があるとしましょう-1,2,3,4,5そして次Array 2の要素があります-6,7,8,9,10

  2. 2つの配列は事前に並べ替えられているため、の最初の要素をの最初の要素と比較しArray 1、Array 2下の要素をに挿入しArray 3ます。

  3. Element 2次に、 ofArray 1とElement 1ofについて同じことを行いArray 2、次に小さい数をポップします

私が言及したアプローチはうまくいくはずですが、私が持っている質問は次のとおりです。

  1. これは最も効率的なアプローチですか？
  2. このプロセスを説明できる専門用語（Binary Search Algoなど）はありますか？
  3. この問題を解決するための他の指針はありますか？
4

3 に答える 3

3

はい、これが最も効率的なアプローチです。

実行されますO(n)（nは両方の配列のサイズです）。これは、配列を1回通過することを意味します。

3番目の配列を作成するには、とにかく各要素を1回実行する必要があります（3番目の配列に正しい順序で追加するだけの場合でも）。

このプロセスは通常呼び出され、マージソートアルゴリズムmergeの一部です。

これがStackOverflowでの実装です。

于 2013-03-21T20:34:00.043 に答える
1

1）これは最も効率的なアプローチであるO（n + m）です。ここで、n-最初の配列のサイズ、m-2番目の配列のサイズ。2）マージソートアルゴリズムのマージルーチンと呼ばれます。

実際には、3つ以上の配列をマージできます。通常、外部ソーティングで使用されるか、スペースに制限がある場合に使用されます。

于 2013-03-21T20:36:33.760 に答える
1

  1. 入力配列がソートされていることがわかっている場合、マージアルゴリズムは線形になります（Big O表記のO（n））。ただし、一方の配列の最大値がもう一方の配列の最小値よりも低いことがわかっている場合は、Array.Copy個々の要素を比較する代わりに使用して、パフォーマンスをさらに向上させることができます。

  2. はい、これはマージアルゴリズムです。

  3. 練習は完璧を作る。私はプロジェクトオイラーの問題を楽しく解決するのが好きです。それらは「小さい」のですが、最初のいくつかを過ぎると、それを解決する方法を本当に考えさせられます。

    才能のために編集：無意味

于 2013-03-21T20:37:20.980 に答える