Java版LeetCode

Appearance

4. 寻找两个正序数组的中位数 ​

数组 二分查找 分治

题目 ​

给定两个大小分别为 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
  • -106 <= nums1[i], nums2[i] <= 106

题解 ​

java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length1 = nums1.length, length2 = nums2.length, length = length1 + length2;
    // 合并数组
    int[] mergeArray = new int[length];

    // 合并数组索引及遍历两个数组的索引
    int i = 0, j = 0, k = 0;
    while (j < length1 && k < length2) {
        // 有序合并
        if (nums1[j] > nums2[k]) {
            mergeArray[i++] = nums2[k++];
        } else {
            mergeArray[i++] = nums1[j++];
        }
    }

    // 数组1剩余部分
    while (j < length1) {
        mergeArray[i++] = nums1[j++];
    }

    // 数组2剩余部分
    while (k < length2) {
        mergeArray[i++] = nums2[k++];
    }

    return
        length % 2 == 0
            // 合并数组长度为偶数
            ? (mergeArray[length / 2] + mergeArray[length / 2 - 1]) / 2.0
            // 合并数组长度为奇数
            : mergeArray[length / 2] / 1.0;
}