leetcode 04 Median of Two Sorted Arrays

n1 为 num1的 len

n2 为 num2的 len

故中间的数应该是 k = (n1 + n2 + 1) / 2

二分 num1中位置 m1 , 故 num2的位置为m2

必须保证 nums1[m1-1] <= nums2[m2]

且nums1[m1] >= nums2[m2-1]

class Solution {

public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        if(nums1.size() > nums2.size())

            return findMedianSortedArrays(nums2, nums1);

        int n1 = nums1.size(), n2 = nums2.size();

        int l = 0, r = n1-1;

        const int k = (n1 + n2 + 1) / 2;

        while(l <= r) {

            int m1 = (l + r) /2;

            int m2 = k - m1;

            if(nums1[m1] <= nums2[m2-1])

                l = m1 + 1;

            else

                r = m1 - 1;

        }

        int m1 = l;

        int m2 = k - l;

        int c1 = max( m1<=0 ? INT_MIN : nums1[m1-1],

                      m2<=0 ? INT_MIN : nums2[m2-1]);

        int c2 = min( m1>=n1 ? INT_MAX : nums1[m1],

                      m2>=n2 ? INT_MAX : nums2[m2] );

        if((n1 + n2) & 1)

            return c1;

        return 0.5 * (c1 + c2);

    }

};

巴特西

leetcode 04 Median of Two Sorted Arrays

最新文章

热门文章