[LeetCode] 4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

input :

• nums1 nums2
• 0 <= len(nums1) <= 1000
• 0 <= len(nums2) <= 1000

output :

• nums1, nums2를 합친 리스트의 median (중간 값)을 출력하시오

조건 :

• nums1, nums2는 정렬이 되어 있는 상태이다.
• O(log(m + n))의 알고리즘을 제안하시오.

---

Solution explain : Solution

idea

주의

슬라이싱에 주의 해야 하며
3번의 else 부분에서 valA 또한 제거해야 한다는 것에 주의하자.

class Solution:
    def medianValue(self, arr1, arr2, targetIdx):
        if not arr1: return arr2[targetIdx]
        if not arr2: return arr1[targetIdx]

        idxA, idxB = len(arr1) // 2, len(arr2) // 2
        valA, valB = arr1[idxA], arr2[idxB]

        # need to fix that valA is always the small one.
        if valA > valB:
            valA, valB = valB, valA
            idxA, idxB = idxB, idxA
            arr1, arr2 = arr2, arr1

        # if idx is 3 then 3 of element is in front of that one.
        cntFrontIdxA = idxA + idxB

        if targetIdx <= cntFrontIdxA:
            # valB can not be ignored
            return self.medianValue(arr1, arr2[:idxB], targetIdx)
        else:
            # valA can be ignored
            return self.medianValue(arr1[:idxA + 1], arr2, targetIdx - idxA + 1)

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        length = len(nums1) + len(nums2)
        targetIdx = length // 2

        val1 = self.medianValue(nums1, nums2, targetIdx)
        if length % 2 == 0:
            val2 = self.medianValue(nums1, nums2, targetIdx - 1)
            return (val1 + val2) / 2

        return val1