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

ゝ一世哀愁。 2023-02-22 07:50 17阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]

##### 解法一 #####

暴力，将两个数组一一比较存到一个新的一维数组中，并保持有序，之后按照奇数偶数进行返回。

class Solution { 
        public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
            int []num = new int[nums1.length+nums2.length];
            int l1 = nums1.length;
            int l2 = nums2.length;
            int i = 0,j=0,k=0;
            while(i<l1&&j<l2){ 
                if(nums1[i]<=nums2[j]){ 
                    num[k]=nums1[i];
                    i++;
                    k++;
                }
                else{ 
                    num[k]=nums2[j];
                    j++;
                    k++;
                }
            }
            while(i < l1){ 
                num[k]=nums1[i];
                i++;
                k++;
            }
            while(j < l2){ 
                num[k]=nums2[j];
                j++;
                k++;
            }
            int ll = num.length;
            if(ll%2!=0){ 
                int t = ll/2;
                return num[t];
            }
            return (num[ll/2]+num[ll/2-1])/2.0;
        }
    }

#### 解法二 ####

二分法 时间复杂度log(m+n)

class Solution { 
        public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
            int l1 = nums1.length;
            int l2 = nums2.length;
            int left = (l1+l2+1)/2;
            int right = (l1+l2+2)/2;
            //奇数偶数统一处理，返回两数之和的平均数，奇数时两个数是相同的
            return (getKth(nums1,0,l1-1,nums2,0,l2-1,left)
            +getKth(nums1,0,l1-1,nums2,0,l2-1,right))/2.0;
        }
        public int getKth(int []nums1,int start1,int end1,
        int []nums2,int start2,int end2,int k){ 
            int len1 = end1 - start1 + 1;
            int len2 = end2 - start2 + 1;
            //判断有一个数组为空的情况直接返回
            if(len1 == 0){ 
                return nums2[start2 + k-1];
            }
            if(len2 == 0){ 
                return nums1[start1 + k-1];
            }
            if(k == 1){ //返回第一小的数，就比较两个数组起始位置的大小
                return Math.min(nums1[start1],nums2[start2]);
            }
            int i = start1 + Math.min(len1,k/2) - 1;
            int j = start2 + Math.min(len2,k/2) - 1;
            if(nums1[i]<nums2[j]){ //判断舍弃两个数组的哪一部分
            //如果A[K/2]<B[K/2]那么在A[K/2]前的数都不可能是第k小的数
                        return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
            }
            else{ 
                return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200702111007716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ==,size_16,color_FFFFFF,t_70