LeetCode - 4 寻找两个正序数组的中位数

题目来源

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

题目描述

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 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
• -10^6 <= nums1[i], nums2[i] <= 10^6

题目解析

本题要求nums1和nums2合并后数组的中位数。

如果一个数组的长度n：

• n是奇数，那么数组的中位数就是 arr[arr.length / 2]，即数组中间位置的元素的值
• n是偶数，那么数组的中位数就是 (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2，即数组中间两个位置的元素的值 / 2

本题的难点主要在于如何将两个有序数组合并为一个新的有序数组。

解题思路很简单，只要定义两个指针 i, j 初始分别指向nums1和nums2的首元素，然后比较nums1[i] 和 nums2[j] 的大小，较小者元素加入到合并数组中，并且对应指针++，然后继续比较，直到某个指针越界。

假设 i 指针越界，那么 j 指针必然不会越界，即必然有一个数组会先遍历完所有元素，另一个数组无法遍历完所有元素，此时我们需要将另一个未遍历完的数组整体加入到合并数组尾部。这样就可以得到一个有序合并数组了。

Java算法源码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        int[] merge = new int[n];

        int i = 0;
        int j = 0;
        int k = 0;

        while(i < nums1.length && j < nums2.length) {
            if(nums1[i] < nums2[j]) {
                merge[k++] = nums1[i++];
            } else {
                merge[k++] = nums2[j++];
            }
        }

        while (i < nums1.length) {
            merge[k++] = nums1[i++];
        }

        while (j < nums2.length) {
            merge[k++] = nums2[j++];
        }

        int mid = n / 2;

        if(n % 2 == 0) {
            return (merge[mid] + merge[mid - 1]) / 2.0f;
        } else {
            return merge[mid];
        }
    }
}

JS算法源码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const n = nums1.length + nums2.length;
    const merge = new Array(n);

    let i = 0;
    let j = 0;
    let k = 0;

    while(i < nums1.length && j < nums2.length) {
        if(nums1[i] < nums2[j]) {
            merge[k++] = nums1[i++];
        } else {
            merge[k++] = nums2[j++];
        }
    }

    while(i < nums1.length) {
        merge[k++] = nums1[i++];
    }

    while(j < nums2.length) {
        merge[k++] = nums2[j++];
    }

    const mid = Math.floor(n / 2);

    if(n % 2 == 0) {
        return (merge[mid] + merge[mid-1]) / 2;
    } else {
        return merge[mid];
    }
};

Python算法源码

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n = len(nums1) + len(nums2)

        merge = [0] * n

        i = 0
        j = 0
        k = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                merge[k] = nums1[i]
                i += 1
            else:
                merge[k] = nums2[j]
                j += 1
            
            k += 1

        while i < len(nums1):
            merge[k] = nums1[i]
            i += 1
            k += 1
        
        while j < len(nums2):
            merge[k] = nums2[j]
            j += 1
            k += 1

        mid = n // 2

        if n % 2 == 0:
            return (merge[mid] + merge[mid - 1]) / 2.0
        else:
            return merge[mid]