[leetcode-4] Median of Two Sorted Arrays

LeetCode-4

Median of Two Sorted Arrays : Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

note : The overall run time complexity should be O(log (m+n)).

Answer

        :::python

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

Result : 93ms Memory: 14mb

Median of Two Sorted Arrays

• 두 개의 정렬된 배열이 주어질 때, 두 배열의 중앙값을 찾는 문제입니다.
• 예를 들어, 배열 A = [1, 3, 5], 배열 B = [2, 4, 6] 이 주어지면, 중앙값은 (3+4)/2 = 3.5 가 됩니다.
• 두 배열의 크기는 같은 경우도 있지만, 다른 경우도 있으므로 코드로 구현할 때에는 이를 고려하여 작성해야 합니다.
• 이 문제는 이진 검색을 활용하여 풀 수 있습니다. 이진 검색이란 배열을 반으로 나누어 탐색하는 방법으로, 시간복잡도는 O(log(n+m)) 입니다.
• 이진 검색을 이용해 두 배열을 나누고, 각각의 중간값을 비교하여 조건에 따라 배열의 왼쪽 또는 오른쪽 부분만 탐색합니다.
• 마지막으로 중앙값을 찾아 반환합니다.