[leetcode] 4. Median of Two Sorted Arrays

원문)

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

번역)

m, n의 사이즈의 정렬된 배열 nums1, nums2가 있다.
2정렬된 배열들의 중앙값을 찾아라. 전체 시간복잡도는 O(log (m+n))이어야 한다.
nums1과 nums2이 모두 빈값이 아니라고 가정한다.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

문제접근

처음 접근방법은 중간값을 구하는 것이니까
두 리스트를 합쳐서 정렬하고, 그 후에 (최소값+최대값) / 2하면 끝?! 이라고 생각했으나..
그렇다면 이게 Hard 레벨은 아니었을것이다..

그게 잘못됬다고 느꼈던 것이.

Input

[3]
[-2,-1]

Output

0.5

Expected

-1.0

해당 테스트 케이스를 보고 느꼈다.

좀 찾아보니 중앙값? 이란게 있다.

• 중앙값(median) 또는 중위수는 어떤 주어진 값들을 크기의 순서대로 정렬했을 때 가장 중앙에 위치하는 값을 의미한다. 예를 들어 1, 2, 100의 세 값이 있을 때, 2가 가장 중앙에 있기 때문에 2가 중앙값이다.
• 값이 짝수개일 때에는 중앙값이 유일하지 않고 두 개가 될 수도 있다. 이 경우 그 두 값의 평균을 취한다. 예를 들어 1, 10, 90, 200 네 수의 중앙값은 10과 90의 평균인 50이 된다.

요놈인듯 보인다.

성공은 했으나, 뭔가 이상하다.
전체 시간복잡도는 O(log (m+n))이어야 한다.
좀 찾아보니 운이 좋아서 합격인듯 하다.
왜냐하면 python 내장 sort는 MergeSort변형 TimSort라고 한다.
어느시간대에도 nlogn를 유지하여 해당 문제에 적합하다.

솔루션을 봤는데, 영어로 적혀있기도 하고 어렵다.
솔루션 정리

정렬된배열을 하나의 정렬된 리스트로만 만들면 되는것 같은데
이를 확인해보니 병합정렬 마지막 단계랑 비슷한것이 아닌가?

최종으로는 이 방법으로 풀었다.

문제코드1

1 2 3 4 5 6

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: nums = nums1 + nums2 nums.sort() return (nums[0] + nums[-1])/ 2

문제코드2

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: nums = nums1 + nums2 nums.sort() m = len(nums) // 2 if len(nums) % 2 == 0: m = len(nums) // 2 n1 = nums[m-1] n2 = nums[m] return (n1 + n2) / 2 else: return float(nums[m])

소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: i = j = 0 l1 = len(nums1) l2 = len(nums2) nums = [] while len(nums) < l1 + l2: if i == l1 or j == l2: if i == l1: nums.append(nums2[j]) j += 1 else: nums.append(nums1[i]) i += 1 else: if nums1[i] < nums2[j]: nums.append(nums1[i]) i += 1 else: nums.append(nums2[j]) j += 1 m = len(nums) // 2 if len(nums) % 2 == 0: m = len(nums) // 2 n1 = nums[m-1] n2 = nums[m] return (n1 + n2) / 2 else: return float(nums[m])