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

解決

ソリューションの 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 <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            // Edge cases
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                // Correct partition
                if ((x + y) % 2 == 0) {
                    return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                } else {
                    return Math.max(maxX, maxY);
                }
            } else if (maxX > 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))) の時間計算量を達成し、大規模な入力配列に適しています。

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