My solution using merge sort in C++ (44ms)


  • -2
    D

    I have corrected my solution. This may be correct.

    class Solution {
    public:
    double min(double a, double b) {
    	return a > b ? b : a;
    }
    double findKthElement(vector<int>& nums1, vector<int>& nums2,int k) {
    	if(nums1.size()>nums2.size())
    		return findKthElement(nums2, nums1, k);
    	if (nums1.size() == 0)return nums2[k - 1];
    	if (k == 1)return min(nums1[0], nums2[0]);
    
    	int ia = min(k / 2, nums1.size());
    	int ib = k - ia;
    
    	if (nums1[ia - 1] < nums2[ib - 1]) {
    		vector<int> v(nums1.begin() + ia, nums1.end());
    		return findKthElement(v, nums2, k - ia);
    	}
    	else if (nums1[ia - 1]>nums2[ib - 1]) {
    		vector<int> v(nums2.begin() + ia, nums2.end());
    		return findKthElement(nums1, v, k - ia);
    	}
    	return nums2[ia - 1];
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	int len = nums1.size() + nums2.size();
    	if (len & 0x1) {
    		return findKthElement(nums1, nums2, (len + 1) / 2);
    	}
    	return 0.5*(findKthElement(nums1, nums2, (len + 1) / 2) + findKthElement(nums1, nums2, (len + 1) / 2+1));
    }
    

    };


  • 0
    A

    This is not O(lg(m+n))
    This is O(m+n).
    And that's just merging. Not merge sort.


  • 0
    L

    i think there's some wrong in your code,

    vector<int> v(nums2.begin() + ia, nums2.end());

    it must be ib not ia


Log in to reply
 

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