[4] [ queue ] Median of Two Sorted Arrays

문제 설명

---

Given two sorted arraysnums1andnums2of sizemandnrespectively, returnthe medianof the two sorted arrays.

The overall run time complexity should beO(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.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

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

---

풀이 과정

---

• 두개 합쳐서 정렬해서 풀 수도 있지만 오래 걸림.

1. 따라서, 우선 두개의 리스트를 queue로 바꾼다.
2. 전체 개수가 홀수일때, 짝수일때 중간값의 위치가 다르다.
   • 홀수일 때 : (두개의 리스트의 길이의 합 // 2)
   • 짝수일 때 : (두개의 리스트의 길이의 합 // 2) - 1, (두개의 리스트의 길이의 합 // 2)
     • 두개를 뽑고 2로 나누어준 값이 중간값
3. 따라서 홀수일 때는 (두개의 리스트의 길이의 합 // 2) - 1개만큼 뽑아주고, 짝수일 때는 (두개의 리스트의 길이의 합 // 2) - 2개만큼 뽑아준다.
   • 이 다음에 홀수일때는 한개 뽑고, 짝수일때는 두개 뽑아서 중간값 구해주면 됨.
4. 뽑아줄 때는 두개의 큐의 가장 왼쪽에서 값을 비교하며 하나씩 뽑아준다.
   • 한쪽이 큰 경우 다른쪽에서 뽑아줌.
   • 이 때, 한쪽 큐가 비는 경우 다른쪽 큐에서만 뽑아주면 된다.

---

소스 코드

---

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        from collections import deque

        q1 = deque(nums1)
        q2 = deque(nums2)

        total_length = len(nums1) + len(nums2)
        even = False

        def next_pop(q1, q2):
            temp = 0
            if q1 and q2:
                if q1[0] > q2[0]:
                    temp = q2.popleft()
                else:
                    temp = q1.popleft()
            elif q1:
                temp = q1.popleft()
            elif q2:
                temp = q2.popleft()
            return temp


        if total_length % 2 == 0:
            even = True
            median_idx = total_length // 2 
        else:
            median_idx = total_length // 2 + 1

        for i in range(median_idx-1):
            next_pop(q1, q2)

        answer = 0
        if even:
            answer = next_pop(q1, q2) + next_pop(q1, q2)
            answer = answer / 2
        else:
            answer = next_pop(q1, q2)

        answer = answer * 1.0

        return answer