O(log(M+N)) solution without recursion


  • 0
    D

    The idea is the same as one of the top voted solutions but the code below does not use recursion.

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len = nums1.size() + nums2.size();
            
            if (len % 2 != 0) {
                // odd number of total elements!
                return (double)findKth(nums1, nums2, len/2+1);
            } else {
                int midL = findKth(nums1, nums2, len/2);
                int midR = findKth(nums1, nums2, len/2+1);
                return (double)(midL + midR) / 2.0;
            }
        }
        
        int findKth(vector<int> nums1, vector<int> nums2, int k) {
            int l1 = nums1.size();
            int l2 = nums2.size();
            int s1 = 0, s2 = 0;
            
            while (1) {
                if (s1 >= l1) {
                    return nums2[s2 + k -1];
                } 
                if (s2 >= l2) {
                    return nums1[s1 + k -1];
                }
                if (k==1) {
                    //cout << nums1[s1] << endl;
                    return min(nums1[s1], nums2[s2]);
                }
                
                int m1 = s1 + k/2 - 1;
                int m2 = s2 + k/2 - 1;
                int mid1 = m1 >= l1 ? INT_MAX : nums1[m1];
                int mid2 = m2 >= l2 ? INT_MAX : nums2[m2];
                if (mid1 > mid2) {
                    s2 = m2 + 1;
                } else {
                    s1 = m1 + 1;
                }
                k -= k/2;
            }
        }
    };
    

Log in to reply
 

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