LeetCode_二分搜索_困难_4.寻找两个正序数组的中位数

蔚落 2023-10-06 17:57 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定两个大小分别为 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

**示例 3：**  
输入：nums1 = \[0,0\], nums2 = \[0,0\]  
输出：0.00000

**示例 4：**  
输入：nums1 = \[\], nums2 = \[1\]  
输出：1.00000

**示例 5：**  
输入：nums1 = \[2\], nums2 = \[\]  
输出：2.00000

**提示：**  
nums1.length == m  
nums2.length == n  
0 <= m <=1000  
0 <= n<=1000  
1 <= m+n <= 2000  
\-106 <= nums1\[i\], nums2\[i\] <= 106

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

## 2.思路 ##

（1）归并算法  
可以参考归并排序中一趟归并算法的思想，先将这两个数组正序归并到另外一个长度为这两个数组长度之和的新数组中，然后在根据新数组长度的奇偶性来求出中位数。此外，由题目还需要注意到两个数组中最多可以有一个为空。**不过显然该算法的时间复杂度超过了O(log(m+n))**。

（2）二分搜索  
要在时间复杂度为 O(log(m+n)) 内找到两个有序数组的中位数，可以使用二分查找算法的变体来解决：

*  首先，假设数组 nums1 的长度小于等于数组 nums2 的长度（如果不是，则交换数组）。
 *  然后，进行二分查找，将数组 nums1 分为两部分，使得：
    
     *  左半部分包含了数组 nums1 中的 `(m + n + 1) / 2` 个最小元素；
     *  右半部分包含了数组 nums1 中的 `(m + n) / 2` 个最大元素；
 *  然后，使用二分查找在数组 nums1 的左半部分进行搜索，找到一个位置 i，使得：
    
     *  `nums1[i - 1] <= nums2[j]` 且 `nums1[i] >= nums2[j - 1]`，其中 `j = (m + n + 1) / 2 - i`。
 *  最后，根据数组 nums1 和数组 nums2 的长度奇偶性，求得中位数：
    
     *  如果 m + n 是奇数，则中位数为 max(nums1\[i - 1\], nums2\[j - 1\])；
     *  如果 m + n 是偶数，则中位数为 (max(nums1\[i - 1\], nums2\[j - 1\]) + min(nums1\[i\], nums2\[j\])) / 2。

## 3.代码实现（Java） ##

//思路1————归并算法
    class Solution {
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
            int len1 = nums1.length;
            int len2 = nums2.length;
            if (len1 == 0) {
        
                return (len2 % 2 == 1) ? (double) nums2[len2 / 2] : (nums2[len2 / 2] + nums2[len2 / 2 - 1]) / 2.0;
            }
            if (len2 == 0) {
        
                return (len1 % 2 == 1) ? (double) nums1[len1 / 2] : (nums1[len1 / 2] + nums1[len1 / 2 - 1]) / 2.0;
            }
            //两数组均不为空
            int newLen = len1 + len2;
            int[] newArr = new int[newLen];
            int i = 0, j = 0, k = 0;
            //将两个数组正序归并到新数组 newArr中(此处与归并排序中的一趟归并算法相似)
            while (i < len1 && j < len2) {
        
                if (nums1[i] < nums2[j]) {
        
                    newArr[k++] = nums1[i++];
                } else {
        
                    newArr[k++] = nums2[j++];
                }
            }
            while (i < len1) {
        
                newArr[k++] = nums1[i++];
            }
            while (j < len2) {
        
                newArr[k++] = nums2[j++];
            }
            //在找出中位数时，需注意元素个数的奇偶性
            return (newLen % 2 == 1) ? (double) newArr[newLen / 2] : (newArr[newLen / 2] + newArr[newLen / 2 - 1]) / 2.0;
        }
    }

//思路2————二分搜索
    class Solution {
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
            int m = nums1.length;
            int n = nums2.length;
            //确保数组 nums1 的长度小于等于数组 nums2 的长度
            if (m > n) {
        
                int[] temp = nums1;
                nums1 = nums2;
                nums2 = temp;
                int tempLen = m;
                m = n;
                n = tempLen;
            }
            //二分查找的初始边界
            int left = 0;
            int right = m;
            //中位数出现的位置
            int halfLen = (m + n + 1) / 2;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                int j = halfLen - mid;
                if (mid < right && nums1[mid] < nums2[j - 1]) {
        
                    left = mid + 1;
                } else if (mid > left && nums1[mid - 1] > nums2[j]) {
        
                    right = mid - 1;
                } else {
        
                    // mid 正好合适
                    int maxLeft;
                    if (mid == 0) {
        
                        maxLeft = nums2[j - 1];
                    } else if (j == 0) {
        
                        maxLeft = nums1[mid - 1];
                    } else {
        
                        maxLeft = Math.max(nums1[mid - 1], nums2[j - 1]);
                    }
                    //如果 m + n 是奇数，直接返回 maxLeft
                    if ((m + n) % 2 == 1) {
        
                        return maxLeft;
                    }
                    int minRight;
                    if (mid == m) {
        
                        minRight = nums2[j];
                    } else if (j == n) {
        
                        minRight = nums1[mid];
                    } else {
        
                        minRight = Math.min(nums1[mid], nums2[j]);
                    }
                    //如果 m + n 是偶数，返回 (maxLeft + minRight) / 2
                    return (maxLeft + minRight) / 2.0;
                }
            }
            //未找到中位数，返回默认值
            return 0.0;
        }
    }