C++ O(log(m+n)) Time, O(1) Space Solution


  • 0
    F
    class Solution {
    public:
        int doFindK(vector<int>& nums1, vector<int>& nums2, int l1, int h1, int l2, int h2, int k)
        {
            if (l1 >= h1) return nums2[k - 1];
            if (l2 >= h2) return nums1[k - 1];
            int total_size = h1 - l1 + h2 - l2;
            if (k >= total_size) return max(nums1[h1-1], nums2[h2-1]);
            if (k <= 0)     return min(nums1[l1], nums2[l2]);
            int ruleout = total_size - k + 1;
            int p1 = ruleout/2 , p2 = ruleout - p1;
            if (p1 > h1 - l1)
            {
                p1 = h1 - l1;
                p2 = ruleout - p1;
            }else if (p2 > h2 - l2)
            {
                p2 = h2 - l2;
                p1 = ruleout - p2;
            }
            int mid1 = h1 - p1, mid2 = h2 - p2;
            if (nums1[mid1] < nums2[mid2])
                return doFindK(nums1, nums2, l1, h1, l2, mid2, k);
            else if (nums1[mid1] > nums2[mid2])
                return doFindK(nums1, nums2, l1, mid1, l2, h2, k);
            else
                return nums1[mid1];
        }
        inline int findK(vector<int>& nums1, vector<int>& nums2, int k)
        {
            return doFindK(nums1, nums2, 0, nums1.size(), 0, nums2.size(), k);
        }
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int sz = nums1.size() + nums2.size();
            if (sz % 2)
                return findK(nums1, nums2, (sz+1)/2);
            return 0.5*(findK(nums1, nums2, sz/2) + findK(nums1, nums2, sz/2+1));
        }
    };

Log in to reply
 

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