LeetCode - 4. Median of Two Sorted Arrays

[LeetCode] 4. Median of Two Sorted Arrays

LeetCode 4번 문제를 풀어보았다.. Link

Problem

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

Intuition

LeetCode 문제를 풀며 처음으로 만난 Hard 문제..

두 Array를 합치고 Sorting한 다음, 성분이 홀수개면 중간값, 짝수개면 중간값들의 평균을 구해 반환하면 되는 간단한 문제이지만,

Overall runtime complexity가 O(log(m+n))이어야해서 패스.. (사실 그냥 이렇게해도 Accept되고, 심지어 성능까지 더 좋지만 문제의 의도와 맞지 않는 듯 하다.)

O(log(m+n))은 O(n)다음으로 빠른 시간복잡도로, 한 Array가 있다고 했을 때 그 성분들을 전부 보지도 않는, 예를들어 Binary search 같은 알고리즘을 사용하면 O(log(m+n))의 시간복잡도를 얻을 수 있다.

이번 문제풀이에도 조건을 충족하기 위해 Binary search 느낌의 풀이방식을 사용(적극 참고)하였다.

Approach

두 Array를 각각 2개의 Sub-Array로 나눠 B와 A를 합칠 위치를 반복문과 조건문으로 조절하여 얻어내기위한 접근 (A와 B는 정렬되어있음)

1. 두 Array를 합친 길이 total를 구하고, 중간위치 half를 구한다
2. 두 Array중 짧은 Array를 A, 긴 것을 B라고 한다.
3. A의 중간위치 i를 구한다. 이때 l과 r은 각각 A의 시작과 끝 인덱스이다.
4. j는 B의 중간위치가 될 변수다.
5. Aleft와 Aright는 각각 A의 왼쪽 Sub-array의 최대값, 오른쪽 Sub-array의 최소값이다.
6. Bleft와 Bright는 각각 B의 왼쪽 Sub-array의 최대값, 오른쪽 Sub-array의 최소값이다.
7. Aleft가 Bright보다 작거나 같고, Aright가 Bleft보다 크거나 같다는 뜻은
   • A의 왼쪽 Sub-array가 B의 왼쪽 Sub-array에 들어가서 정렬하고, A의 오른쪽 Sub-array가 B의 오른쪽 Sub-array에 들어가서 정렬했을 때, 왼쪽 어레이의 모든 성분은 오른쪽 어레의 모든 성분보다 작거나 같다는 것 이다.
   • Array의 길이가 홀수면 A의 왼쪽 Sub-array와 B의 왼쪽 Sub-array의 길이를 half로 고정하였기 때문에 Aright와 Bright중 더 작은 값을 반환한다.
   • 짝수면 Left값 중에 Max값과 Right 값중에 Min값을 구하고 1/2하여 반환한다.
8. Aleft가 Bright보다 크다는 뜻은 A의 왼쪽 Sub-array가 B의 오른쪽 Sub-array보다 큰 값이 있다는 것이기 때문에 A의 왼쪽 Sub-array를 줄이기위해 r에 i-1을 대입한다.
9. 이외의 경우에는 A의 왼쪽 Sub-array가 작다는 뜻으로 l에 i+1을 대입한다.
10. 성립할 때까지 3-9를 반복한다.

Complexity

• Time complexity:

  Total을 N이라고 할 때 \(O(log N)\)

• Space complexity: 모름

My Code

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        if len(B) < len(A):
            A, B = B, A

        l, r = 0, len(A) - 1
        while True:
            i = (l + r) // 2
            j = half - i - 2

            Aleft = A[i] if i>=0 else float("-infinity")
            Aright = A[i+1] if i+1 < len(A) else float("infinity")
            Bleft = B[j] if j>=0 else float("-infinity")
            Bright = B[j+1] if j+1 < len(B) else float("infinity")


            if Aleft <= Bright and Bleft <= Aright:
                # Odd
                if total % 2:
                    return min(Aright, Bright)
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1

솔직히 l과 r을 업데이트 해주는 부분이 잘 이해가 안가긴하지만.. 어쩔 수 없다..

다음에 다시 풀어봐야겠다.

참고한 비디오 링크: https://www.youtube.com/watch?v=q6IEA26hvXc

아래에 대충 썼는데 생각지도 못하게 통과했던 코드를 같이 첨부하겠다.

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