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

ゝ一纸荒年。 2024-02-23 05:36 17阅读 0赞

#### 题目来源 ####

[4. 寻找两个正序数组的中位数 - 力扣（LeetCode）][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]

[4. _ - _LeetCode]: https://leetcode.cn/problems/median-of-two-sorted-arrays/description/