本文共 3806 字，大约阅读时间需要 12 分钟。

4. 寻找两个正序数组的中位数：

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

样例 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

分析

这道题第一感觉是合并两个数组再排序，然后直接取中位数，代码量很少，然而很明显时间复杂度和空间复杂度都上去了，相当于把两个有序数组当作无序数组使用了。对于有序这个性质怎么用，官方题解已经很给力了，我无需再赘述，参考了官方和网友的题解。

题解

java

class Solution {
       public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           int m = nums1.length;        int n = nums2.length;        if (m > n) {
               return this.findMedianSortedArrays(nums2, nums1);        }        int left  = 0;        int right = m;        // 中位数下标和        int midSum = (m + n + 1) / 2;        while (left < right) {
               // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            int i = (left + right + 1) / 2;            int j = midSum - i;            if (nums1[i - 1] > nums2[j]) {
                   right = i - 1;            } else {
                   left = i;            }        }        int i = left;        int j = midSum - left;        // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]        int nums_im1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];        int nums_i   = i == m ? Integer.MAX_VALUE : nums1[i];        int nums_jm1 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];        int nums_j   = j == n ? Integer.MAX_VALUE : nums2[j];        // median1：前一部分的最大值        int median1 = Math.max(nums_im1, nums_jm1);        // median2：后一部分的最小值        int median2 = Math.min(nums_i, nums_j);        if ((m + n) % 2 == 0) {
               return (median1 + median2) / 2.0;        } else {
               return median1;        }    }}

rust

impl Solution {    pub fn find_median_sorted_arrays(nums1: Vec
   
    , nums2: Vec
    
     ) -> f64 {        let (m,n) = (nums1.len(), nums2.len());        if (m > n) {            return Solution::find_median_sorted_arrays(nums2, nums1);        }        let (mut left, mut right) = (0, m);        let mid_sum = (m + n + 1) / 2;        while left < right {            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            let i = (left + right + 1) / 2;            let j = mid_sum - i;            if nums1[i - 1] > nums2[j] {                right = i - 1;            } else {                left = i;            }        }        let (i, j) = (left, mid_sum - left);        // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]        let nums_im1 = match i {            0 => i32::MIN,            _ => nums1[i - 1]        };        let nums_i = match i {            i if i == m => i32::MAX,            _ => nums1[i]        };        let nums_jm1 = match j {            0 => i32::MIN,            _ => nums2[j - 1]        };        let nums_j = match j {            j if j == n => i32::MAX,            _ => nums2[j]        };        // median1：前一部分的最大值        let mut median1 = nums_im1.max(nums_jm1);        // median2：后一部分的最小值        let mut median2 = nums_i.min(nums_j);        if (m + n) % 2 == 0 {            (median1 + median2) as f64 / 2.0        } else {            median1 as f64        }    }}
    
   

最后说两句

非常感谢你阅读本文章，如果你觉得本文对你有所帮助，请留下你的足迹，点个赞，留个言，多谢~

作者水平有限，如果文章内容有不准确的地方，请指正。

希望小伙伴们都能每天进步一点点。

本文由博客原创，转载请注明来源，谢谢~

转载地址：https://le-yi.blog.csdn.net/article/details/116938209 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！