【leetcode】两个排序数组中的中位数（Median of Two Sorted Arrays）【python】

梦里梦外; 2022-05-14 00:21 157阅读 0赞

![这里写图片描述][70]  
**需要注意两点**

1.  可能存在一个数组遍历完毕的情况，这时候只需要遍历另外一个数组
2.  数组可能为空，必须事先进行判断，否则会越界  
    **算法思想**  
    **一次遍历两个数组，将较小的加入到新数组sums中，这样sums就是有序的，跟合并两个有序的链表的思想一样**

class Solution:
        def findMedianSortedArrays(self, nums1, nums2):
            """ :type nums1: List[int] :type nums2: List[int] :rtype: float 排序数组，可以首先通过两个数组的大小确定中位数的位置 然后通过比较两个数组的元素大小，直接找出中位数 """
            len1 = len(nums1)
            len2 = len(nums2)
            length = len1 + len2
            nums = [0] * length
            i, j, f1, f2 = 0, 0, 0, 0
            if len1 == 0:
                nums = nums2
            elif len2 == 0:
                nums = nums1
            else:
                for index in range(length):
                    if nums1[i] < nums2[j] and f1 == 0:
                        nums[index] = nums1[i]
                        if i != len1 - 1:
                            i += 1
                        else:
                            f1 = 1
                    elif nums1[i] < nums2[j] and f1 == 1:
                        nums[index] = nums2[j]
                        if j != len2 - 1:
                            j += 1
                    elif nums1[i] >= nums2[j] and f2 == 0:
                        nums[index] = nums2[j]
                        if j != len2 - 1:
                            j += 1
                        else:
                            f2 = 1
                    else:
                        nums[index] = nums1[i]
                        if i != len1 - 1:
                            i += 1
            print(nums)
            if length % 2 == 1:
                return nums[int(length / 2)]
            else:
                Median_index1 = int(length / 2) - 1
                Median_index2 = int(length / 2)
                return float((nums[Median_index1] + nums[Median_index2]) / 2)
    
    nums1 = [ ]
    nums2 = [1]
    sol = Solution()
    print(sol.findMedianSortedArrays(nums1, nums2))

[70]: /images/20220514/0e0fe10b2b0743c98e439b47117fbc36.png