算法题：寻找两个正序数组的中位数

蔚落 2022-12-27 07:35 122阅读 0赞

### 算法题：寻找两个正序数组的中位数 ###

*  题目描述
 *   *  示例
     *  提示
 *  代码
 *  执行效率

# 题目描述 #

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

## 示例 ##

示例 1：  
输入：nums1 = \[1,3\], nums2 = \[2\]  
输出：2.00000  
解释：合并数组 = \[1,2,3\] ，中位数 2

示例 2：  
输入：nums1 = \[1,2\], nums2 = \[3,4\]  
输出：2.50000  
解释：合并数组 = \[1,2,3,4\] ，中位数 (2 + 3) / 2 = 2.5

示例 3：  
输入：nums1 = \[0,0\], nums2 = \[0,0\]  
输出：0.00000  
示例 4：  
输入：nums1 = \[\], nums2 = \[1\]  
输出：1.00000

示例 5：  
输入：nums1 = \[2\], nums2 = \[\]  
输出：2.00000

## 提示 ##

nums1.length == m
    nums2.length == n
    0 <= m <= 1000
    0 <= n <= 1000
    1 <= m + n <= 2000
    -106 <= nums1[i], nums2[i] <= 106

# 代码 #

class Solution:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            new_num = []
            i, j = 0, 0
            num_len = len(nums1) + len(nums2)
            print(num_len)
            while len(new_num) <= num_len / 2 :
                print(i,j)
                if i == len(nums1):
                    new_num.append(nums2[j])
                    j+=1
                elif j == len(nums2):
                    new_num.append(nums1[i])
                    i+=1
                else:
                    if nums1[i] < nums2[j]:
                        new_num.append(nums1[i])
                        i += 1
                    else:
                        new_num.append(nums2[j])
                        j += 1
            print(new_num)
            if num_len % 2 == 0:
                return (new_num[num_len//2-1] + new_num[num_len//2])/2
            else:
                return new_num[(num_len-1)//2]

# 执行效率 #

2091 个测试用例  
执行用时: 136 ms  
内存消耗: 12.9 MB

解题思路及代码来源：博主  
题目来源：力扣（LeetCode）  
题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays  
题目著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。