Leetcode: (Python)(Arrays) Median of Two Sorted Arrays

題目連結：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

題意說明：

• 給定兩個遞增的 list
• 找出中位數
• 要在 O(n)時間內

初始想法

1. 確定中位數是一個數字還是兩個數字的平均
2. 逐一比較 list中最小的數字，直到找到中位數

實作程式碼

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total_len = len(nums1)+len(nums2)

        if total_len%2 == 0:
            left_position = total_len/2 - 1
            right_position = total_len/2
        else:
            left_position = total_len//2
            right_position = total_len//2
        
        for i in range(total_len):
            if len(nums1) == 0:
                tmp_value = nums2[0]
                nums2.pop(0)
            elif len(nums2) == 0:
                tmp_value = nums1[0]
                nums1.pop(0)
            elif nums1[0] <= nums2[0]:
                tmp_value = nums1[0]
                nums1.pop(0)
            else:
                tmp_value = nums2[0]
                nums2.pop(0)

            if i == left_position:
                left_value = tmp_value
            if i == right_position:
                right_value = tmp_value

        return float(left_value+right_value)/2

慘不忍睹 . . .

反思一：right value和 list總長度是奇數偶數無關

實作程式碼

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total_len = len(nums1)+len(nums2)
        
        # 將 right_position 拉出來
        # left_position用 right_position數值，不要用 len()
        right_position = total_len//2

        if total_len%2 == 0:
            left_position = right_position - 1
        else:
            left_position = right_position
            
        for i in range(total_len):
            if len(nums1) == 0:
                tmp_value = nums2[0]
                nums2.pop(0)
            elif len(nums2) == 0:
                tmp_value = nums1[0]
                nums1.pop(0)
            elif nums1[0] <= nums2[0]:
                tmp_value = nums1[0]
                nums1.pop(0)
            else:
                tmp_value = nums2[0]
                nums2.pop(0)

            if i == left_position:
                left_value = tmp_value
            if i == right_position:
                right_value = tmp_value

        return float(left_value+right_value)/2

速度稍微提昇

反思二：找到中位數就回傳，不等迴圈結束

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total_len = len(nums1)+len(nums2)

        right_position = total_len//2

        if total_len%2 == 0:
            left_position = right_position - 1
        else:
            left_position = right_position
            
        for i in range(total_len):
            if len(nums1) == 0:
                tmp_value = nums2[0]
                nums2.pop(0)
            elif len(nums2) == 0:
                tmp_value = nums1[0]
                nums1.pop(0)
            elif nums1[0] <= nums2[0]:
                tmp_value = nums1[0]
                nums1.pop(0)
            else:
                tmp_value = nums2[0]
                nums2.pop(0)

            if i == left_position:
                left_value = tmp_value
            if i == right_position:
                right_value = tmp_value
                return float(left_value+right_value)/2

數值可以再提昇一些