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

要求

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

示例

输入：nums1 = [1,3], nums2 = [2]

输入：nums1 = [1,2], nums2 = [3,4]

提示

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106
• 时间复杂度为 O(log (m+n)) （这样就要求利用数组有序的特点）

代码

class Solution {        public double findMedianSortedArrays(int[] A, int[] B) {        int m = A.length;        int n = B.length;        if (m > n) {             return findMedianSortedArrays(B,A); // 保证 m <= n        }        int iMin = 0, iMax = m;        while (iMin <= iMax) {            // 二分找出i的位置            int i = (iMin + iMax) / 2;            // 根据个数推算出j的位置，表达式A            int j = (m + n + 1) / 2 - i;            // 下面是为了让两数组从i和j划分得到的左部分的数都小于右部分的数，并且j是根据个数得到的，这样中位数就确定了。            if (j != 0 && i != m && B[j-1] > A[i]){ // 根据表达式A，左下比右上大，则左下要更小的数，j小，则i需要增大                iMin = i + 1;             }            else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要减小                iMax = i - 1;             }            else { // 达到要求，并且将边界条件列出来单独列举                int maxLeft = 0;                // 如果第一个数组左边没元素                if (i == 0) { maxLeft = B[j-1]; }                // 如果第二个数组左边没元素                else if (j == 0) { maxLeft = A[i-1]; }                // 都有元素则取两者最大值                else { maxLeft = Math.max(A[i-1], B[j-1]); }                if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分                int minRight = 0;                // 如果第一个数组右边没元素                if (i == m) { minRight = B[j]; }                // 如果第二个数组右边没元素                else if (j == n) { minRight = A[i]; }                // 都有元素则取两者最小值                else { minRight = Math.min(B[j], A[i]); }                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果            }        }        return 0.0;    }}

转载地址：http://axbpn.baihongyu.com/