Leetcode刷题笔记

一、二分法

题目：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 

O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
看到时间复杂度为log 要求的，就需要先想一想二分法递归实现：

题解思路：两数组中位数二分法题解

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(m>n){
            return findMedianSortedArrays(nums2,nums1);
        }
        int l = 0, h = 2 * m,L1 = 0,L2 = 0,R1 = 0, R2 = 0,c1=0,c2=0;
        while(l<=h){
            c1 = (l + h)/2;
            c2 = m + n -c1;
            L1 = (c1 == 0)? Integer.MIN_VALUE : nums1[(c1-1)/2];
            R1 = (c1 == 2 * m)? Integer.MAX_VALUE : nums1[c1/2];
            L2 = (c2 == 0)? Integer.MIN_VALUE : nums2[(c2-1)/2];
            R2 = (c2 == 2 * n)? Integer.MAX_VALUE : nums2[c2/2];
            if(L1>R2){
                h = c1-1;
            }else if(L2>R1){
                l = c1+1;
            }else{
                break;
            }
        }
        return (Math.max(L1,L2)+Math.min(R1,R2))/2.0;
        
    }
}