[Python] #4. Median of Two Sorted Arrays(Hard)

문제 #4. Add Two NumbersMedian of Two Sorted Arrays(Medium)

이 문제는 두개의 정렬된 array가 주어졌을 때 두개의 array를 합쳐 median값을 구하는 문제이다.

먼저 시도한 방법은 두개의 array를 일일이 비교해서 merge한 이후에 median값을 계산하는 것이였다. 코드는 아래와 같다. 

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        len1 = len(nums1)
        len2 = len(nums2)
        array = []
        lt = 0
        rt = 0
        while len1 and len2:
            if nums1[lt]> nums2[rt]:
                array.append(nums2[rt])
                rt +=1
                len2 -=1 
            else:
                array.append(nums1[lt])
                lt +=1
                len1 -=1
        print(len1,len2)
        if len1:
            array += nums1[lt:]
        elif len2:
            array += nums2[rt:]
            
        print(array)
        length = len(array)
        if length % 2 ==1 :
            return array[length//2]
        else:
            return (array[(length//2)-1] + array[(length//2)])/2

두 개의 array를 값을 일일이 비교해 합친 이후에 median 값을 계산했다.  결과는 아래와 같다.

속도는 96ms, 메모리는 14.1MB 소모했다. 

다음 방법은 일일이 비교하지 않고 python list자료구주에 내장함수를 활용해서 해결하는 방법이다.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1.extend(nums2)
        nums1 = sorted(nums1)
        length = len(nums1)
        if length %2 == 1:
            return nums1[length//2]
        else:
            return (nums1[(length//2)-1] + nums1[(length//2)])/2

결과는 아래와 같다.

96ms 시간과 14.1MB의 메모리를 소모했다.