[LeetCode/python]4. Median of Two Sorted Arrays

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

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

뭔가 너무 어렵게 푼 기분이라 다시 풀어봤다.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        arr = nums1+nums2
        arr.sort()
        l, r= 0,len(arr)-1
        while l<=r:
            if l==r:
                return arr[l]
            l+=1
            r-=1
        return (arr[l]+arr[r])/2

1. 주어진 리스트 두 개를 합친 후, 솔팅한다.

2. 왼쪽 포인터를 의미하는 l과 오른쪽 포인터를 의미하는 r을 선언해준다.

3. l에는 제일 처음 인덱스를 넣어주고, r에는 제일 마지막 인덱스를 넣어준다.

4. while문은 l이 r보다 작거나 같을때까지 반복된다.

5. l==r 일 때, 즉 arr의 길이가 홀수 일때를 의미하며, 이 때는 해당 인덱스에 있는 값이 midian 값이 된다.

6. l!=r 일 때는 각 포인터를 이동시켜준다.

7. while문을 탈출했을 때는 l>r일 것. 즉, 짝수 길이의 배열일 때를 뜻한다. l과 r이 가리키는 값들의 중간 값이 답이 되므로 (arr[l]+arr[r])/2를 return 해준다.

(여기서 l과 r이 엇갈리는 것에 의미를 두지 않아도 된다. 어차피 두 값의 중간 값이 답이 되므로.) 

 

이분탐색으로 풀면 다음과 같은 결과가 나옴.