leetcode 刷题（数组篇）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

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

LeetCode

解法

方法一 暴力搜索

直接合并两个数组，时间复杂度为O(n+m)，空间复杂度为O(1)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int[] mid = new int[2];
        // 定义两个指针
        int i = 0, j = 0, k = 0;
        while (i + j <= (len >> 1)) {
            k = i + j == (len >> 1) ? 1 : 0;
            if (i <= m - 1 && j <= n - 1) {
                mid[k] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
            }
            else if (i == m) {
                mid[k] = nums2[j++];
            }
            else {
                mid[k] = nums1[i++];
            }
        }
        if ((len & 1) == 1) {
            return mid[1];
        }
        else {
            return (mid[0] + mid[1])/2.0;
        }
    }
}

Accepted
2094/2094 cases passed (2 ms)
Your runtime beats 100 % of java submissions
Your memory usage beats 32.02 % of java submissions (39.8 MB)

方法二 二分查找

用二分查找找到第k小的数字，时间复杂度为O(log(m+n))，空间复杂度为O(1)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        if ((len & 1) == 1) {
            int midIdx = len >> 1;
            double mid = getKthElement(nums1, nums2, midIdx + 1);
            return mid;
        }
        else {
            int midIdx1 = len >> 1 - 1;
            int midIdx2 = len >> 1;
            double mid = (getKthElement(nums1, nums2, midIdx1 + 1) + getKthElement(nums1, nums2, midIdx2 + 1))/ 2.0;
            return mid;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int offset1 = 0, offset2 = 0;

        while (true) {
            // 边界情况，返回终值
            // 1.有一个数组遍历完
            if (offset1 == m){
                return nums2[offset2 + k - 1];
            }
            if (offset2 == n){
                return nums1[offset1 + k - 1];
            }
            // 2.k值为1
            if (k == 1) {
                return Math.min(nums1[offset1], nums2[offset2]);
            }

            // 正常情况
            // 判断索引, 是否会出界
            int mid = k >> 1;
            int idx1 = Math.min(offset1 + mid, m) - 1;
            int idx2 = Math.min(offset2 + mid, n) - 1;
            
            // 判断索引值大小, 更新k值和偏移量
            if (nums1[idx1] <= nums2[idx2]) {
                k -= (idx1 - offset1 + 1); // 正常情况如果不出界，就是减去mid
                offset1 = idx1 + 1;
            }
            else {
                k -= (idx2 - offset2 + 1);
                offset2 = idx2 + 1;
            }
        }
    }
}