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

小鱼儿 2024-02-20 09:04 74阅读 0赞

## 1. 题目 ##

见 [寻找两个正序数组的中位数][Link 1]

## 2. 解题思路 ##

首先一看到题目说是正序数组，且时间复杂度要求在对数级别，所以自然想到了双指针中的二分法。  
![在这里插入图片描述][0dae4a6d6cb94985b2eb57efda781e88.png]  
首先来看一下，假设输入是这两个数组，那么将其逻辑合并成一个大数组的话，分界线左边为大数组的左边，右边同理。这个数组又是升序的，且原来的两个数组是升序的（即L1<=R1& L2<=R2）。所以在大数组中，`L1<=R2` & `L2<=R1`  
所以这里就得到了第一个约束：切割后的中位线要满足交叉小于等于。  
然后大数组的中位数呢，就是从中位数左边选择一个大的数字（Max(L1,L2)）和右边选一个小的数字（`Min（R1，R2）`）来进行计算。

上面的情况是刚好属于一个逻辑合并数组并且划分中位线后 满足`交叉小于`的情况，假如像下图划分中位线后不满足交叉小于呢？  
![在这里插入图片描述][81308c6753f046eb94e45f022814c36a.png]  
因为L2>R1了，所以我们右移R1，直到比L2大，满足交叉小于等于。  
![在这里插入图片描述][5342106b150145c1bbe35b13fa42c605.png]  
这个时候会奇怪了，为什么要移动nums2的中位线？  
因为此时我们做了一个逻辑合并数组的设想，所以整个大数组中位线两边的元素应该尽量保持相同。  
R1移动后nums1中位线左边有5个元素，所以同理移动nums2的中位线，让它的右边也有5个元素。

另外需要注意的是：  
1、我们默认只对nums1进行操作，由nums1的操作计算出对nums2的操作。比如 假如不符合交叉小于等于，那么我们就移动nums1的中位线，然后由公式算出nums2的中位线即可。  
2、当数组为奇数的时候我们默认把中位线划分在右边一点（左边也是可以的）  
![在这里插入图片描述][1addfb74fd7242fab354f41d4b8ee1f5.png]

**上面说的是两个数组都是偶数的情况，假如有个数字为奇数呢？**  
![在这里插入图片描述][58ac10e8b2994babae076ca529ae27a7.png]  
因为数组是有序的，且满足交叉小于等于，**且奇数数组的中位数都是划分在右边的（我们约定的）**，单拎出来nums2看的话，中位数是中位线左边的那个。所以最后逻辑合并大数组了，中位数只要在大数组中位线左边取偏大的就行了。也就是max（L1，L2）

## 3. 代码 ##

class Solution {
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
            //保持数组长度小的在前面，节省性能
            if (nums1.length > nums2.length) {
        
                return findMedianSortedArrays(nums2, nums1);
            }
    
            int m = nums1.length;
            int n = nums2.length;
            int left = 0, right = m;
            int median1 = 0, median2 = 0;
    
            while (left <= right) {
        
                //确定第一个数组的分割线
                median1 = (left + right) / 2;
                //确定第二个数组的分割线
                median2 = (m + n + 1) / 2 - median1;
    
                //数组1中位分割线左边的数
                int L1= (median1 == 0 ? Integer.MIN_VALUE : nums1[median1 - 1]);
                //数组1中位分割线右边的数
                int R1= (median1 == m ? Integer.MAX_VALUE : nums1[median1]);
                //数组2中位分割线左边的数
                int L2= (median2 == 0 ? Integer.MIN_VALUE : nums2[median2 - 1]);
                //数组2中位分割线右边的数
                int R2= (median2 == n ? Integer.MAX_VALUE : nums2[median2]);
                int nums_j = (median2 == n ? Integer.MAX_VALUE : nums2[median2]);
    
                if (L1 > R2) {
        
                    //不符合交叉小于等于 继续二分(左移中位线)
                    right = median1-1;
                } else if (L2 > R1) {
        
                    //不符合交叉小于等于 继续二分(右移中位线)
                    left = median1 + 1;
                } else {
        
                 //将所有的数合并后，如果是偶数个数，中位数是中间两个数的平均值，如果是奇数个数，中位数是大的数
                   return (m + n) % 2 == 0 ? (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0 :  Math.max(L1, L2);
                }
            }
         return 0.0;
        }
    
    }

[Link 1]: https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/1117545/4-xun-zhao-liang-ge-zheng-xu-shu-zu-de-z-pwja/
[0dae4a6d6cb94985b2eb57efda781e88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/934a2adc9b5746648f7a679b5dc24625.png
[81308c6753f046eb94e45f022814c36a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/4f3400e8c935491a83d47ac652e2db2d.png
[5342106b150145c1bbe35b13fa42c605.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/ca492faf34d44494a0e1ef9cd3dbea6e.png
[1addfb74fd7242fab354f41d4b8ee1f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/acc11747ca1b47bcbd1d42cdfbd6bfc7.png
[58ac10e8b2994babae076ca529ae27a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/17f6db271e5c417e8555987c222c6cbb.png