[LeetCode/릿코드] - 4. Median of Two Sorted Arrays - (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)). 

문제 설명 :

두 개의 리스트가 주어진다. 각 리스트는 크기가 다르며 두 개의 리스트의 모든 값들 중에서 중간 값을 반환해야 한다. 시간 복잡도는
O(log (m+n)) 이어야 한다.

아이디어 :

1. 시간 복잡도와 데이터 제한을 봤을때, 반복문으로 문제를 풀 수 없다.
2. 중간 값을 구하려면, 모든 값의 상태를 알아야 하기 때문에 sort를 사용했다. 최악의 경우 O(NlogN)
3. 시간복잡도도 넘지 않고, 정렬을 하면 인덱스만으로 중간 값을 구할 수 있다.
4. 복잡하지 않게 리스트를 합쳐서 정렬했다.
5. 중간값을 구할 때 예외를 생각하여, 배열의 전체 크기가 0, 1, 짝수, 홀수 일 때를 나눴다.

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
-10^6 <= nums1[i], nums2[i] <= 10^6

 

정답 코드

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1 += nums2
        nums1.sort()
        nLen = len(nums1)
        if nLen == 1:
            return nums1[0]
        elif nLen > 1:
            if nLen % 2 != 0:
                return nums1[nLen//2]
            else:
                mIdx = nLen // 2
                return (nums1[mIdx - 1] + nums1[mIdx]) / 2
        return 0

소스코드를 짜는 것보다 아이디어를 생각하는데 시간이 걸릴 것 같다. 

 

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