寻找两个有序数组的中位数

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

思路1

第一种简单的思路是将这两个数组合并成一个，然后找到中位数即可。

package com.longhujing.leetcode.t0004;

/**
 * @author lonhujing
 * @date 2020-02-01
 */
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];
        int i = 0, j = 0, index = 0;
        while (i < nums1.length || j < nums2.length) {
            int val1 = i < nums1.length ? nums1[i] : Integer.MAX_VALUE;
            int val2 = j < nums2.length ? nums2[j] : Integer.MAX_VALUE;
            int temp = Math.min(val1, val2);
            if (temp == val1) {
                i++;
            } else {
                j++;
            }
            nums[index++] = temp;
        }
        return nums.length % 2 != 0 ? nums[nums.length / 2] :
                (nums[nums.length / 2] + nums[nums.length / 2 - 1]) / 2.0;
    }

}

思路2

其实并没有必要将两个数组合并到一起，由于这两个数组是有序的，那么我们只需要找到中间的那一个数或者中间的那两个数即可。

package com.longhujing.leetcode.t0004;

/**
 * @author lonhujing
 * @date 2020-02-01
 */
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = 0, n2 = 0, i = 0, j = 0;
        int len = nums1.length + nums2.length, mid = len / 2;
        while (mid >= 0) {
            int val1 = i < nums1.length ? nums1[i] : Integer.MAX_VALUE;
            int val2 = j < nums2.length ? nums2[j] : Integer.MAX_VALUE;
            int temp = Math.min(val1, val2);
            if (val1 == temp) {
                i++;
            } else {
                j++;
            }
            n1 = n2;
            n2 = temp;
            mid--;
        }
        return len % 2 != 0 ? n2 : (n1 + n2) / 2.0;
    }

}

思路3

前面两种算法的时间复杂度都达到了O(m + n)，然而题目要求的是O(log(m + n))。由于数组是排好序的，完全可以用二分的方式来解决这道题目。

假设两个数组如下，需要找到的中位数为第7个数字。分别选取两个数组的第k / 2 = 3个数。

由于3 < 4，因此把第二个数组的1 2 3排除掉，那么问题就转化为找到第7 - 3 = 4个数了。

仍然重复上述的步骤，直到k == 1的时候，求得最终的结果。

package com.longhujing.leetcode.t0004;

/**
 * @author lonhujing
 * @date 2020-02-01
 */
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int left = (nums1.length + nums2.length + 1) / 2;
        int right = (nums1.length + nums2.length + 2) / 2;
        return (helper(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, left) +
                helper(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, right)) / 2.0;
    }

    private int helper(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int k) {
        int len1 = e1 - s1 + 1, len2 = e2 - s2 + 1;
        if (len1 > len2) {
            return helper(nums2, s2, e2, nums1, s1, e1, k);
        }
        if (len1 == 0) {
            return nums2[s2 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int i = s1 + Math.min(len1, k / 2) - 1, j = s2 + Math.min(len2, k / 2) - 1;
        if (nums1[i] > nums2[j]) {
            return helper(nums1, s1, e1, nums2, j + 1, e2, k - (j - s2 + 1));
        } else {
            return helper(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1));
        }
    }

}