[Leetcode] 4. Median of Two Sorted Arrays

문제

 

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

Median of Two Sorted Arrays - LeetCode

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)).

1. 배열 nums1과 배열 nums2가 주어질 때 두 배열의 중간값을 반환하라.

2. 시간복잡도는 O(log(m+n))

 

Example 1:

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

Example 2:

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

 

문제풀이 코드

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        merge = sorted(nums1)
        if len(merge) % 2 == 0:
            mid1, mid2 = len(merge) // 2 - 1, len(merge) // 2
            return (merge[mid1] + merge[mid2]) / 2
        else:
            mid = len(merge) // 2
            return float(merge[mid])

1. nums1과 nums2의 중간값을 구하기위해 nums1과 nums2를 합쳐준다

  - 방법1. nums1.extend(nums2)

  - 방법2. nums1 + nums2(파이썬은 배열두개를 더하면 합쳐진다.)

  - 방법3. heapq.merge를 이용하는 방법 등 여러가지 방법이 존재한다

2. 합쳐진 nums1을 정렬해주고 중간값을 구한다.

3. merge의 길이가 짝수일 때 중간에 해당하는 두개의 값을 더하고 2로 나눈값을 반환한다.

4. merge의 길이가 홀수일 때 중간값을 반환한다.