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. 中央値の計算: パーティションに基づいて中央値を計算します。

解決

ソリューションの詳細な Java 実装は次のとおりです:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low  minY) {
                high = partitionX - 1;
            } else {
                low = partitionX   1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

説明

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

結論

この二分探索アプローチは、2 つのソートされた配列の中央値を見つけるための効率的なソリューションを提供します。より小さな配列で二分探索を活用することで、このソリューションは O(log(min(m, n))) の時間計算量を実現し、大規模な入力配列に適しています。