Concise c++11 solution


  • 0
    P
    typedef vector<int> vi;
    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            auto f = [&nums1, &nums2](int k){ //we suppose that k is always greater than 0
                if(nums1.empty()) return nums2[k-1];
                if(nums2.empty()) return nums1[k-1];
                int l = max(0, k - (int)nums2.size()), r = min(k, (int)nums1.size());
                while(l<r-1){
                    int c = (l+r)/2;
                    if(nums1[c-1]<nums2[k-c-1]) l = c;
                    else r = c;
                }
                int candi1 = (l?max(nums1[l-1],nums2[k-l-1]):nums2[k-l-1]);
                int candi2 = (k-r?max(nums1[r-1],nums2[k-r-1]):nums1[r-1]);
                return min(candi1,candi2);
            };
            int n = nums1.size() + nums2.size();
            if(n%2) return (double)f(n/2+1);
            else return 0.5*(f(n/2) + f(n/2+1));
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.