Median of Two Sorted Arrays

Q: 두 정렬된 배열의 중앙값을 구하는 알고리즘의 시간 복잡도는 무엇인가요?

분할 지점에 대한 이진 탐색은 더 짧은 목록에서 가능한 분할 지점을 매 단계 절반으로 줄이므로 O(log(min(m, n))) 시간과 O(1) 공간이 걸립니다. 병합에는 O(m + n) 이 걸립니다. 길이가 각각 3000인 두 목록의 경우 약 12단계로 6000에 대응하는 작업을 수행합니다.

Q: 왜 더 짧은 배열에서 이진 검색을 할까요?

j = half-i 이기 때문입니다. i 가 더 짧은 목록의 범위에 있으면 j 는 0과 더 긴 목록의 길이 사이에 유지되므로, 모든 읽기는 범위 안에 있거나 무한대로 취급하는 끝을 지나게 됩니다.

Q: 부동소수점 없이 중앙값을 어떻게 반환하나요?

가운데 두 값을 정수로 더하세요. 짝수인 합은 2로 나누세요. 합이 홀수이면 절댓값의 절반을 쓰고 .5 를 붙이세요. 합이 음수이면 마이너스 기호를 붙입니다. -1은 "-0.5" 가 됩니다.

어려움이진 탐색

+10

정수 목록 nums1과 nums2를 받습니다. 각 목록은 가장 작은 값부터 가장 큰 값 순으로 정렬되어 있으며, 값이 하나 이상 들어 있습니다. 두 목록의 모든 값을 합친 중앙값을 텍스트로 반환하세요.

전체 값의 개수가 홀수이면 중앙값은 가운데 값입니다. 예를 들면 "4"입니다. 개수가 짝수이면 가운데 두 값의 평균입니다. 예를 들면 "2.5" 또는 "-0.5"입니다. 정수는 소수점 없이 쓰고, 0은 "0"으로 쓰며, 절대로 "-0"으로 쓰지 마세요. 시간 복잡도는 O(log(min(m, n)))를 목표로 하세요.

함수

findMedianSortedArrays(nums1: integer-array, nums2: integer-array) → string

nums1integer-array: 첫 번째 목록을 가장 작은 값부터 가장 큰 값 순으로 정렬합니다
nums2integer-array: 두 번째 목록, 가장 작은 값부터 가장 큰 값 순으로 정렬됨
반환값string: 모든 값의 중앙값으로, "4" 또는 "-2.5"와 같은 텍스트

제약 조건

1 ≤ nums1.length, nums2.length ≤ 3000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
두 목록은 비내림차순으로 정렬되어 있으며, 값이 반복될 수 있습니다.

예제

입력: nums1 = [1, 4]nums2 = [2, 7, 9]
출력: "4"
설명: 값을 함께 나열하면 1, 2, 4, 7, 9입니다. 값이 다섯 개이므로 가운데 값은 하나이며, 세 번째 값인 4입니다.

후속 질문

같은 분할 방법을 사용해 두 목록에서 임의의 k번째로 작은 값을 로그 시간에 찾을 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

두 목록을 병합하면 O(m + n) 시간에 중앙값을 구할 수 있지만, 읽는 값 대부분은 답을 바꿀 수 없습니다. 중앙값은 하위 절반과 상위 절반 사이의 경계가 어디에 놓이는지에 따라 달라지며, 숫자 하나로 그 경계를 정할 수 있습니다. 더 짧은 목록에서 하위 절반에 포함할 값의 개수입니다. 이분 탐색은 O(log(min(m, n))) 단계 만에 그 값을 찾습니다.

두 목록을 병합하기

핵심 아이디어

병합 정렬에서 하는 방식대로 목록을 병합해 정렬된 하나의 목록 merged를 만듭니다. total = m + n일 때 정수 나눗셈을 사용해 merged[(total-1)/2]와 merged[total/2]를 더합니다. 전체 개수가 홀수이면 두 값 모두 가운데 값이고, 짝수이면 가운데에 있는 두 값이므로 어느 경우든 합의 절반이 중앙값입니다.

가운데에서 멈추더라도 병합 과정에서 값의 절반을 넘게 살펴보므로 시간 복잡도는 O(m + n)입니다.

알고리즘

리스트를 merged에 병합하면서 매번 현재 값 중 더 작은 값을 선택한 다음, 남은 리스트의 나머지를 추가합니다.
total = m + n일 때, merged[(total-1)/2]와 merged[total/2]를 더합니다.
합의 절반을 텍스트로 반환합니다. 합이 짝수이면 2로 나누고, 홀수이면 부호와 절댓값의 절반, .5를 씁니다.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Merge the two sorted lists into one, the way merge sort does.
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    total = len(merged)
    # For an odd total both indexes point at the one middle value.
    return half_text(merged[(total - 1) // 2] + merged[total // 2])

분할 지점에 대한 이진 탐색

핵심 아이디어

아래쪽 절반에 half = (m+n+1)/2개의 값을 둡니다. 전체 개수가 홀수일 때는 하나를 더 둡니다. nums1의 앞에서 i개의 값을 가져오고, nums2의 앞에서 j = half-i개의 값을 가져옵니다. 아래쪽에 있는 어떤 값도 위쪽에 있는 어떤 값보다 크지 않을 때 분할이 올바른 것입니다. 각 목록은 정렬되어 있으므로 두 가지 조건만 확인하면 됩니다. left1 ≤ right2 및 left2 ≤ right1입니다. 여기서 left는 목록이 아래쪽 절반에 넣는 마지막 값이고, right는 목록이 남겨 두는 첫 번째 값입니다. 한쪽에 값이 없으면 음의 무한대 또는 양의 무한대로 간주합니다.

left1 > right2이면 i가 너무 큽니다. left2 > right1이면 너무 작습니다. 따라서 i는 0부터 m까지의 이진 탐색 대상입니다. [1, 2]와 [3, 4]에서는 i = 1일 때 left2 = 3 > right1 = 2이므로 조건을 만족하지 않고, i = 2일 때 조건을 만족합니다. (2 + 3) / 2 = 2.5입니다.

알고리즘

nums1를 더 짧은 목록으로 만들고, half = (m+n+1)/2로 둡니다.
lo = 0부터 hi = m까지 i를 이진 탐색하고, j = half-i로 둡니다.
left1 = nums1[i-1], right1 = nums1[i], left2 = nums2[j-1], right2 = nums2[j]를 읽고, 끝을 넘어서면 무한대로 간주합니다.
left1 > right2이면 hi = i-1로 설정합니다. left2 > right1이면 lo = i+1로 설정합니다.
그렇지 않고 전체 개수가 홀수이면 max(left1, left2)를 반환합니다. 짝수이면 max(left1, left2) + min(right1, right2)를 2로 나눕니다.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Binary search over the shorter list.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2   # size of the left half; it gets the extra value when m + n is odd
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # values the left half takes from nums1
        j = half - i          # values it takes from nums2
        # An empty side counts as minus or plus infinity.
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1        # too many values from nums1
        elif left2 > right1:
            lo = i + 1        # too few values from nums1
        else:
            left_max = max(left1, left2)
            if (m + n) % 2 == 1:
                return str(left_max)
            return half_text(left_max + min(right1, right2))
    return ""  # not reached: sorted input always has a valid split

함정과 경계 사례

부동소수점으로 나누기. Python은 정수인 중앙값을 3.0으로 출력하고, C의 %f는 2.5를 2.500000으로 출력합니다. 합은 정수로 유지하세요.
음수인 홀수 합에 정수 몫과 .5를 붙여 쓰기. C와 Java에서 -1 / 2는 0이므로 -0.5가 0.5가 되고, Python에서 -5 // 2는 -3이므로 -2.5가 -3.5가 됩니다. 절댓값을 반으로 나눈 다음 부호를 다시 붙이세요.
-0을 쓰기. 가운데 값 -1과 1의 합은 0이며, 답은 "0"입니다. 합에서 부호를 가져오세요.
더 긴 리스트를 검색하기. j = half-i가 0보다 작아지거나 n을 넘을 수 있습니다. 먼저 리스트를 서로 바꾸세요.
i = 0일 때 nums1[i-1]을 읽기. [9]와 [1, 2]에서처럼 발생할 수 있습니다. 값이 없는 경우에는 무한대를 사용하세요.

자주 묻는 질문3

두 정렬된 배열의 중앙값을 구하는 알고리즘의 시간 복잡도는 무엇인가요?

분할 지점에 대한 이진 탐색은 더 짧은 목록에서 가능한 분할 지점을 매 단계 절반으로 줄이므로 O(log(min(m, n))) 시간과 O(1) 공간이 걸립니다. 병합에는 O(m + n)이 걸립니다. 길이가 각각 3000인 두 목록의 경우 약 12단계로 6000에 대응하는 작업을 수행합니다.

왜 더 짧은 배열에서 이진 검색을 할까요?

j = half-i이기 때문입니다. i가 더 짧은 목록의 범위에 있으면 j는 0과 더 긴 목록의 길이 사이에 유지되므로, 모든 읽기는 범위 안에 있거나 무한대로 취급하는 끝을 지나게 됩니다.

부동소수점 없이 중앙값을 어떻게 반환하나요?

가운데 두 값을 정수로 더하세요. 짝수인 합은 2로 나누세요. 합이 홀수이면 절댓값의 절반을 쓰고 .5를 붙이세요. 합이 음수이면 마이너스 기호를 붙입니다. -1은 "-0.5"가 됩니다.

def findMedianSortedArrays(nums1, nums2):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

nums1 = [1, 4]
nums2 = [2, 7, 9]

예상 출력

"4"