快乐的LeetCode --- 寻找两个正序数组的中位数

古城微笑少年丶 2023-02-11 11:27 13阅读 0赞

**题目描述：**

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

假设 nums1 和 nums2 不会同时为空。

**示例 1:**

nums1 = [1, 3]
    nums2 = [2]
    
    则中位数是 2.0

**示例 2:**

nums1 = [1, 2]
    nums2 = [3, 4]
    
    则中位数是 (2 + 3)/2 = 2.5

--------------------

**解题思路:**

将两个数组合并为一个数组，然后排序，找出中位数

--------------------

**代码：**

class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            nums = []
            for i in range(len(nums1)):
                nums.append(nums1[i])
            for j in range(len(nums2)):
                nums.append(nums2[j])
            nums = sorted(nums)
            if len(nums) % 2 == 0:
                return (nums[len(nums)//2] + nums[(len(nums)//2)-1]) / 2.0
            else:
                return nums[len(nums)//2]

代码简化1：

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

代码简化2：

class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            nums = nums1 + nums2
            nums = sorted(nums)
            if len(nums) % 2 == 0:
                return (nums[len(nums)//2] + nums[(len(nums)//2)-1]) / 2.0
            else:
                return nums[len(nums)//2]

更多数组合并的简化技巧参考博客：[Python合并多个数组][Python]

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/median-of-two-sorted-arrays][https_leetcode-cn.com_problems_median-of-two-sorted-arrays]

[Python]: https://blog.csdn.net/weixin_43283397/article/details/106301741
[https_leetcode-cn.com_problems_median-of-two-sorted-arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays