[1스4코2파] # 194. LeetCode 4. Median of Two Sorted Arrays

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (194차)
[4코1파] 2023.01.13~ (186일차)
[1스4코1파] 2023.04.12~ (97일차)
[1스4코2파] 2023.05.03 ~ (75일차)

Today :

2023.07.16 [194일차]
binary_search
LeetCode 4. Median of Two Sorted Arrays

LeetCode 4. Median of Two Sorted Arrays

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

문제 설명

두 개의 오름차순으로 정렬된 배열이 주어질 때, 이 배열을 merge 했을 때 오름차순으로 정렬되어있는 배열에서 midean 값을 return 하기
시간복잡도가 O(log(m+n)) 이여야 함..

문제 풀이 방법

주어진 배열 두 개의 길이의 half를 가지고 더 작은 길이의 배열의 원소의 left, right를 가지고 더 긴 길이의 배열의 원소의 left, right를 가지고 핸들링 하는건데

중앙값을 기준으로 배열은 작은 요소들의 집합과 큰 요소들의 집합으로 나뉘게 된다.
중앙값 성질에 따라서

이걸 배열에 있는 인덱스에 적용해보면

이따위로 되는 듯

내 코드

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

        left, right= 0, len(A) - 1
        while True:
            i = (left + right) // 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)
                # even
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft > Bright:
                right = i - 1
            else:
                left = i + 1

증빙

여담

어렵잖아 모르겠고 수영이나 갈랜다