Kimuksung
Kimuksung 안녕하세요. 분산처리에 관심이 많은 생각하는 주니어 Data Enginner입니다.

leet code python 4

leet code python 4

4. Median of Two Sorted Arrays

문제 풀이 과정을 아래 이미지로 대채합니다.

  • 어려운 문제만 표출되도록 구성하였습니다. (일반적인 코딩테스트 풀이 문제는 아래 태그에서 확인 하면 됩니다.)
    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
    
    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(A) > len(B):
              A, B = B, A
            
          left, right = 0, len(A)-1
    
          while True:
              mid = (left+right)//2 #A
              j = half-mid-2 # B
                
              Aleft= A[mid] if mid >= 0 else float("-infinity")
              Aright = A[mid+1] if (mid+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")
              print(total,half,mid,j, Aleft, Aright, Bleft,Bright)
              if Aleft <= Bright and Bleft <= Aright:
                  print(total,half,mid,j, A, B, max(Aleft, Bleft), min(Aright, Bright))
                  if total % 2:
                      return min(Aright, Bright)
                  return (max(Aleft, Bleft)+min(Aright, Bright))/2
              elif Aleft > Bright:
                  right = mid - 1
              else:
                  left = mid + 1
    

Leetcode4-1 Leetcode4-2 Leetcode4-3 Leetcode4-4 Leetcode4-5 Leetcode4-6 Leetcode4-7