반응형

4. Median of Two Sorted Arrays (Hard)

 

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

 

You may assume nums1 and nums2 cannot be both empty.

 

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

 

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

 

 

Java Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int fullLength = nums1.length + nums2.length;
        int midCount = 2 - (fullLength % 2);
        int cnt = fullLength >> 1;
        double mid = 0;

        int i = 0;
        int j = 0;

        while (cnt >= 0) {
            int tmpMid;

            if (i < nums1.length && j < nums2.length) {
                tmpMid = (nums1[i] > nums2[j]) ? nums2[j++] : nums1[i++];
            } else {
                tmpMid = (i >= nums1.length) ? nums2[j++] : nums1[i++];
            }

            if (cnt < midCount) {
                mid += tmpMid;
            }
            cnt--;
        }

        return mid / midCount;
    }
}

 

Kotlin Solution

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val fullLength = nums1.size + nums2.size
        val midCount = 2 - fullLength % 2
        var cnt = fullLength shr 1

        var mid = 0.0
        var i = 0
        var j = 0

        while (cnt >= 0) {
            val tmpMid: Int =
                if (i < nums1.size && j < nums2.size) {
                    if (nums1[i] > nums2[j]) nums2[j++] else nums1[i++]
                } else {
                    if (i >= nums1.size) nums2[j++] else nums1[i++]
                }

            if (cnt < midCount) {
                mid += tmpMid.toDouble()
            }
            cnt--
        }
        return mid / midCount
    }
}

 

 

이 외에도 다양한 문제들의 해답 코드를 깃헙 저장소에서 확인할 수 있습니다. (Java, Kotlin)


 

 

반응형
반응형