JavaScript を使用して 2 つの順序付きリストの中央値問題を解決するサンプル コード

数値を小さいものから大きいものへと並べます。このとき、真ん中に位置する変数の値を中央値と呼びます。

では、2 つの順序付きリストが与えられた場合、それらの共通中央値を見つけるにはどうすればよいでしょうか?

この問題が発生したとき、最初に思いつく解決策は、2 つの順序付きリストをマージし、次にそれらを昇順に並べ替え、最後に中央値を一度に取り出すことです。

このアプローチは非常にシンプルで便利ですが、並べ替えのため効率的ではないため、O(N*logN)のアルゴリズムとなります。

それでは、どうやって最適化するのでしょうか?

順序付き線形リストをマージするためのアルゴリズムを参照できます:

1. 2 つのポインターを使用して現在の順序付きリストを指し、新しい array を使用して比較された小さい配列要素を受け取ります。

2. 2 つのポインターが指す配列要素を比較し、小さい方を新しい配列に格納し、ポインターを後方に移動します。このプロセスは、ポインターの 1 つが空になるまで、または中央値が新しい配列によって受信されるまで継続され、その後中央値が直接返されます。

3.フェーズ 2 が完了した後、ポインタが null でなく、この時点で新しい配列で中央値が受け取られていない場合は、中央値が得られるまでポインタを使用して順序付きリストをトラバースし続けます。値を受信し、それを返します。

4.最適化されたアルゴリズムはO(m+n)であり、効率が大幅に向上します。

りー

以上がJavaScript を使用して 2 つの順序付きリストの中央値問題を解決するサンプル コードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。