C++ version using iterator


  • 2
    B
    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int k = nums1.size() + nums2.size();
            if (k % 2 == 0)
                return (findKthSortedArrays(nums1.begin(), nums1.size(), nums2.begin(), nums2.size(), k/2) +
                        findKthSortedArrays(nums1.begin(), nums1.size(), nums2.begin(), nums2.size(), k/2 + 1)
                        ) / 2;
            else
                return findKthSortedArrays(nums1.begin(), nums1.size(), nums2.begin(), nums2.size(), k/2 + 1);
        }
    
    private:
        double findKthSortedArrays(vector<int>::const_iterator nums1, int m, vector<int>::const_iterator nums2, int n, int k) {
            if (m > n)
                return findKthSortedArrays(nums2, n, nums1, m, k);
            
            if (m == 0)
                return *(nums2 + k - 1);
                
            if (k == 1)
                return min(*nums1, *nums2);
                
            int mk = min(m, k / 2);
            int nk = k - mk;
            if (*(nums1 + mk - 1) == *(nums2 + nk - 1))
                return *(nums1 + mk - 1);
            else if (*(nums1 + mk - 1) < *(nums2 + nk - 1))
                return findKthSortedArrays(nums1 + mk, m - mk, nums2, n, k - mk);
            else
                return findKthSortedArrays(nums1, m, nums2 + nk, n - nk, k - nk);
        }
    };

Log in to reply
 

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