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

https://www.bilibili.com/video/av67548632/?redirectFrom=h5
https://v.qq.com/x/page/t0723bjt99a.html
尾扫描

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int k1 = (m+n)/2;
        int k2 = (m+n)/2+1;
        double value1 = find_num(k2, nums1 , nums2);
        if((m+n)%2 != 0) {
            return value1;
        }
        double value2 = find_num(k1, nums1 , nums2);
        return (value1+value2)/2;

    }
    public static double find_num(int k , int [] nums1 , int[] nums2) {
        double ans = 0;
           int m = nums1.length-1;
        int n = nums2.length-1;
        while(k>0&&m>=0&&n>=0) {
            k--;
            int temp1 = nums1[m];
            int temp2 = nums2[n];
            if(temp1>temp2) {
                ans = temp1;
                m--;
            }
            else {
                ans = temp2;
                n--;
            }
        }
        while(k>0&&m>=0) {
            ans = nums1[m];
            m--;
            k--;
        }
        while(k>0&&n>=0) {
            ans = nums2[n];
            n--;
            k--;
        }
        return ans ;
    }
}

二分

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if(total%2==0) {
            int value1 = findKth(nums1 ,0 ,nums2 ,0 ,total/2+1);
            int value2 = findKth(nums1 ,0 ,nums2 ,0 ,total/2 );
            return (value1+value2)/2.0;

        }
        else 
            return findKth(nums1 ,0 ,nums2 ,0 ,total/2+1);
    }
    public static int findKth(int nums1[] , int i ,int []nums2 , int j ,int k) {
        if(nums1.length- i > nums2.length - j )return findKth(nums2, j, nums1, i, k);
        if(nums1.length == i)return nums2[j + k - 1];
        if(k==1)return Math.min(nums1[i],nums2[j]);
        int si = Math.min(i + k / 2,nums1.length);
        int sj = j + k /2 ;
        if(nums1[si-1]>nums2[sj-1]) {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else return findKth(nums1, si, nums2, j, k - (si - i));
        }
}

另外的题解

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
        }
    //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        if(k == 1){
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
    }
}