LeetCode No4 寻找两个正序数组的中位数

本文主要是介绍LeetCode No4 寻找两个正序数组的中位数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

给定两个大小分别为 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

提示：

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

思路

暴力解法

如果不考虑时间复杂度的要求，这道题可以用暴力去解决，根据中位数的定义，中位数一定是有序序列的中间一位或者两位的平均值，那么我只要同时开始遍历两个数组，找到中间的两个数，然后根据两个数组长度总和的奇偶，奇数的话就取小值，偶数就取两者的平均数。

二分查找

暴力的解法固然可以AC，但是还是不满足题目中对于时间复杂度的要求，而且对于这种在有序的数组中找数的题目，第一反应都是用二分去做，只是这题比较特殊，是要在两个数组里面求合并后的值，当然我们可以合并数组后再二分查找，但事实上，既然暴力解法我们都不需要真正的合并数组，那使用二分查找的时候肯定也可以不用。
于是我们再看下中位数的定义：

中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。

既然中位数可以将数值集合划分为相等的两部分，那么我们先在一个数组里面看中位数，将数组从中间分割开来，中位数一定在坐标i和i-1两个数中，如果是数组长度为奇数那么取min(nums[i-1], nums[i])，而如果是偶数则为 (nums[i-1]+nums[i])/2。

    1 3 5 | 8(i) 9

    2 4 6 | 7(i) 10 12

同样如果是两个数组，将两个数组从中间分隔开，使得左边的数据个数=右边的数据个数或者左边比右边多一个，那这个时候基本上就能确定中位数的位置了

    1 3 5 | 8(i) 9
    2 4 6 | 7(j) 10 12

当然仅仅只是数量上满足条件当然还不够，如果中位数就在分割线附近的话，那么分割线附近的4个数，在合并两个数组后应该是一个连续字串，也就是需要满足
nums1[i-1]<=nums2[j] && nums1[j-1]<=nums2[i]
这个条件，于是我们二分查找的条件也就出来了，但是还是需要注意如下四种边界情况。

1 2 3(i) |
| 4（j） 5 6 7

| 4(i) 5 6
1 2 3 4(j) |

1 2 3(i) |
| 4（j） 5 6

| 4（i） 5 6 
1 2 3(j) |

AC代码

暴力解法

点击查看代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        boolean flag = (n+m)%2==0;
        int mid = (n+m)/2+1;
        int i = 0, j = 0;
        int a = 0, b = 0;
        int cnt = 1;
        while( i<n || j < m ) {
            a = b;
            if( i!=n ) {
                if( j!=m ) {
                    if( nums1[i] < nums2[j] ) {
                        b = nums1[i];
                        i ++;
                    } else {
                        b = nums2[j];
                        j ++;
                    }
                } else {
                    b = nums1[i];
                    i ++;
                }
            } else {
                b = nums2[j];
                j ++;
            }
            if( cnt == mid ) {
                break;
            }
            cnt ++;
        }
        if( flag ) {
            return (a+b)/2.0;
        }
        return b;
    }
}

二分查找

点击查看代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        if( n > m ) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0;
        int rigth = n;
        int i = 0;
        int j = 0;

        // 定义的分割线需要满足 nums1[i-1]<=nums2[j] && nums1[j-1]<=nums2[i]
        // 1 3 5 | 8(i) 9
        // 2 4 6 | 7(j) 10 12
        // 左边数字个数应该为 (n+m+1)/2 = i + j
        while( left<rigth ) {
            i = (left + rigth +1 ) / 2;
            j = (n+m+1)/2-i;
            // 二分确定能满足条件的分割线
            if( nums1[i-1]>nums2[j] ) {
                rigth = i - 1;
            } else {
                left = i;
            }
        }
        i = left;
        j = (n+m+1)/2-i;
        // 边界处理
        int numsI1 = i==0? Integer.MIN_VALUE: nums1[i-1];
        int numsI = i==n? Integer.MAX_VALUE: nums1[i];
        int numsJ1 = j==0? Integer.MIN_VALUE: nums2[j-1];
        int numsJ = j==m? Integer.MAX_VALUE: nums2[j];
        if( (n+m)%2 == 1 ) {
            return Math.max(numsI1, numsJ1);
        } else {
            return (Math.max(numsI1, numsJ1) + Math.min(numsI, numsJ)) * 0.5;
        }
    }
}

这篇关于LeetCode No4 寻找两个正序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程