Java でソートされた 2 つの配列の中央値を求める

JAVA チュートリアル
Java ファイル

導入

2 つのソートされた配列の中央値を見つける問題は、コーディング面接の古典的な質問です。課題は、時間計算量 O(log(min(m, n))) で中央値を効率的に見つけることです。ここで、m と n は 2 つの配列のサイズです。この記事では、この効率を達成するために二分検索を採用する Java ソリューションについて説明します。

問題文

2 つのソートされた配列 nums1 と nums2 が与えられた場合、2 つのソートされた配列の中央値を見つけます。全体的な実行時の複雑さは O(log(min(m, n))) になるはずです。ここで、m と n は 2 つの配列のサイズです。

アプローチ

この問題を解決するには、2 つの配列のうち小さい方に対して二分探索アプローチを使用します。目標は、左半分に右半分の要素以下のすべての要素が含まれるように両方の配列を分割することです。段階的な説明は次のとおりです:

1. nums1 が小さい配列であることを確認してください: 二分探索を容易にするために、nums1 が小さい配列であることを確認してください。
2. バイナリ検索の実行: nums1 でバイナリ検索を使用して、正しいパーティションを見つけます。
3. パーティション化: 左側に下位の要素が含まれ、右側に上位の要素が含まれるように両方の配列をパーティション化します。
4. 中央値の計算: パーティションに基づいて中央値を計算します。

リーリー

1. 初期化: nums1 が小さい配列であることを確認します。
2. バイナリ検索: nums1 でバイナリ検索を実行して、正しいパーティションを見つけます。
3. 分割と中央値の計算: 左の要素の最大値と右の要素の最小値を計算して中央値を見つけます。

以上がJava でソートされた 2 つの配列の中央値を求めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。