[Python-Leetcode] 4. Median of Two Sorted Arrays (difficulty : Hard - ☆☆☆)

문제 설명

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

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

 

문제풀이

list1, list2를 비교하여 큰값부터 pop을 실시하여 leng/2인 지점을 찾아 값을 리턴하는 방식으로 코드를 구현하였습니다.

import math

class Solution:
    def findMedianSortedArrays(self, l1, l2) -> float:
        self._cnt = 0
        self.l1 = l1
        self.l2 = l2
        self._ans = []
        
        # define the lenght
        leng1, leng2 = len(self.l1), len(self.l2)

        total_leng = leng1+leng2
        if total_leng % 2==0:
            _case = 0 # even
        else:
            _case = 1 # odd

        half_leng = math.ceil(total_leng/2)
    
        while self.l1 or self.l2:
            # stop case
            if len(self._ans) == half_leng:
                
                if _case == 0: # case even
                    self.l1, self.l2, self._ans = self.list_comparison(self.l1, self.l2, self._ans)
                    return sum(self._ans[-2:])/2
                
                else:
                    print(self._ans[-1])
                    return float(self._ans[-1])
            self.l1, self.l2, self._ans = self.list_comparison(self.l1, self.l2, self._ans)
            
        return float(self._ans[-1])
        
    def list_comparison(self, l1, l2, ans):
        if (l1 and l2):
            if l1[-1] < l2[-1]:
                ans.append(l2.pop())
            else:
                ans.append(l1.pop())
        elif l1:
            ans.append(l1.pop())
        elif l2:
            ans.append(l2.pop())
        return l1, l2, ans