干翻HOT100😡

更新: 12/19/2024 字数: 0 字 时长: 0 分钟

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

题目

题目很简单，就是给了俩正序数组，让用log（m+n）的时间复杂度求中位数

思路

log（m+n）<——> 二分/分治

难点

1. 关联分治

   简单的分治都是在一个数组中不断的二分，而这里涉及到了两个数组的关联二分

   我们每次在两个数组中去找中位数一半的一半的位置，进而进行二分

   之所以找中位数一半的一半，是因为只有这样，才能对后续两者进行合理的比较

2. K是什么？

   k是从1开始的，这一点其实不难发现

   简单理解k为中位数的位置其实不大准确，我们应该明白k是在怎样的一个情况下才是中位数

   我们每一次循环，其实是构建了两个新的数组，然后在新的数组中重新定位中位数的位置去找

   故k应该是新构建的数组中k的值

3. 什么时候结束

   我们除了两种特殊情况外，海春在

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1=nums1.length,l2=nums2.length;
        int L=l1+l2;
        if(L%2==1){
            return getKthElement(nums1,nums2,L/2+1);
        }else{
            return (getKthElement(nums1,nums2,L/2+1)+getKthElement(nums1,nums2,L/2))/2.0;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int index1=0,index2=0,l1=nums1.length,l2=nums2.length;

        while (true){
            if(index1==l1){
                return nums2[index2+k-1];
            }
            if(index2==l2){
                return nums1[index1+k-1];
            }
            if(k==1){ 
                return  Math.min(nums1[index1], nums2[index2]);
            }

            int m=k/2;
            int newIndex1=Math.min(l1-1,index1+m-1);
            int newIndex2=Math.min(l2-1,index2+m-1);
            int e1=nums1[newIndex1];
            int e2=nums2[newIndex2];

            if(e1<e2){
                k-=(newIndex1-index1+1);
                index1=newIndex1+1;
            }else {
                k-=(newIndex2-index2+1);
                index2=newIndex2+1;
            }
        }
    }
}