与えられた二つの昇順にソートされた配列 nums1（長さ m）と nums2（長さ n）から、これらを結合した際の中央値を特定する方法について解説します。

この問題の最適解は通常 O(log (m+n)) の時間計算量が求められますが、ここではまず、より直感的で実装しやすい O(m+n) のアプローチを紹介します。

問題の詳細と制約

配列 nums1 と nums2 はそれぞれ昇順にソートされています。

制約条件:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

具体例

例 1：

<strong>入力：</strong>nums1 = [1,3], nums2 = [2]
<strong>出力：</strong>2.00000
<strong>解説：</strong>結合された配列は [1,2,3] となり、中央値は 2 です。

例 2：

<strong>入力：</strong>nums1 = [1,2], nums2 = [3,4]
<strong>出力：</strong>2.50000
<strong>解説：</strong>結合された配列は [1,2,3,4] となり、中央値は (2 + 3) / 2 = 2.5 です。

解法: 配列のマージによる中央値の特定

この方法では、二つのソート済み配列 nums1 と nums2 を一つにまとめ、新しいソート済み配列 mergedArray を作成します。その後、この mergedArray から中央値を計算します。

アルゴリズムのステップ:

1. 新しい配列 mergedArray を、nums1 と nums2 の合計長（m + n）で初期化します。
2. nums1 用のポインタ（pointer1）、nums2 用のポインタ（pointer2）、および mergedArray 用のポインタ（currentMergedIndex）をそれぞれ 0 に設定します。
3. pointer1 が nums1 の範囲内、かつ pointer2 が nums2 の範囲内にある間、以下の比較を行います:
   • nums1[pointer1] と nums2[pointer2] を比較し、値が小さい方の要素を mergedArray[currentMergedIndex] に格納します。
   • 格納した要素側のポインタと currentMergedIndex をそれぞれ 1 増加させます。
4. 上記のループが終了した後、いずれかの配列にまだ残っている要素があれば、それらをすべて mergedArray の末尾に順次追加します。
5. mergedArray の構築が完了したら、その全長 totalLength に基づいて中央値を計算します。
   • totalLength が奇数の場合、中央値は mergedArray[totalLength / 2] です。
   • totalLength が偶数の場合、中央値は (mergedArray[totalLength / 2 - 1] + mergedArray[totalLength / 2]) / 2.0 です。

計算量:

• 時間計算量: O(m + n)。二つの配列のすべての要素を一度ずつ走査し、マージする必要があるためです。
• 空間計算量: O(m + n)。マージされた配列を格納するために、合計長に等しい追加のメモリ空間が必要になるためです。

Javaによる実装例

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int totalLength = len1 + len2;

        int[] mergedArray = new int[totalLength];
        int pointer1 = 0; // nums1の現在位置を示すポインタ
        int pointer2 = 0; // nums2の現在位置を示すポインタ
        int currentMergedIndex = 0; // mergedArrayの現在位置を示すポインタ

        // 両方の配列にまだ要素がある間、小さい方をmergedArrayに追加
        while (pointer1 < len1 && pointer2 < len2) {
            if (nums1[pointer1] <= nums2[pointer2]) {
                mergedArray[currentMergedIndex++] = nums1[pointer1++];
            } else {
                mergedArray[currentMergedIndex++] = nums2[pointer2++];
            }
        }

        // nums1に残りの要素があれば、すべてmergedArrayに追加
        while (pointer1 < len1) {
            mergedArray[currentMergedIndex++] = nums1[pointer1++];
        }

        // nums2に残りの要素があれば、すべてmergedArrayに追加
        while (pointer2 < len2) {
            mergedArray[currentMergedIndex++] = nums2[pointer2++];
        }

        // マージされた配列から中央値を計算
        if (totalLength % 2 == 1) { // 要素の合計数が奇数の場合
            return mergedArray[totalLength / 2];
        } else { // 要素の合計数が偶数の場合
            int midIndexLeft = totalLength / 2 - 1;
            int midIndexRight = totalLength / 2;
            return (double) (mergedArray[midIndexLeft] + mergedArray[midIndexRight]) / 2.0;
        }
    }
}