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

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/median-of-two-sorted-arrays/

中文链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题目详述

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

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

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

示例 1:

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

则中位数是 2.0

示例 2:

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

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

题目详解

  • 原问题难以直接递归求解，所以我们先考虑这样一个问题：在两个有序数组中，找出第 k 个数。
  • 如果该问题可以解决，那么第 (n + m) / 2 个数就是我们要求的中位数。
  • 先从简单情况入手，假设 m、n >= k / 2，各取前 k /2 个元素，比较 nums1[k / 2 − 1] 与 nums2[k / 2 − 1]。
    • 如果 nums1[k / 2 − 1] > nums2[k / 2 − 1]，则说明 nums2[k / 2 − 1] 及其之前的元素不可能是第 k 大的元素，这部分元素可以淘汰掉，在剩下的元素中找第 k - k / 2 个数。
    • 如果 nums1[k / 2 − 1] <= nums2[k / 2 − 1] ，同理也可以将 nums1 前面一半元素可以淘汰掉，问题规模缩小了一半。
  • 现在考虑边界情况，如果 m < k / 2，比较 nums1[m − 1] 与 nums2[k / 2 − 1]（由于 k = (n + m ) / 2，因此 m、n 不可能同时小于 k / 2）。淘汰的规则同上。
  • 时间复杂度为 O(log(m + n))。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class LeetCode_00004 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if ((total & 1) == 0) {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    private int findKthNumber(int[] nums1, int i, int[] nums2, int j, int k) {
        if (nums1.length - i > nums2.length - j) {  // 保证 nums1 为长度较小者
            return findKthNumber(nums2, j, nums1, i, k);
        }
        if (nums1.length == i) {                    // nums1 区间为空
            return nums2[j + k - 1];
        }
        if (k == 1) {                               // 取两者第一个元素进行比较
            return Math.min(nums1[i], nums2[j]);
        }
        int si = Math.min(i + k / 2, nums1.length), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1]) {
            return findKthNumber(nums1, i, nums2, sj, k - k / 2);
        } else {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
}