C++ solution 29ms


  • 0
    C
    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	if (nums1.empty()) {
    		return nums2.size() % 2 == 0 ? (nums2[(nums2.size() - 1) / 2] + nums2[nums2.size() / 2]) / 2.0f : nums2[nums2.size() / 2];
    	}
    	if (nums2.empty()) {
    		return nums1.size() % 2 == 0 ? (nums1[(nums1.size() - 1) / 2] + nums1[nums1.size() / 2]) / 2.0f : nums1[nums1.size() / 2];
    	}
    	int i = 0, j = 0;
    	int size = nums1.size() + nums2.size();
    	int mid = (nums1.size() + nums2.size() - 1) / 2;
    	while (i + j < mid)
    	{
    		if (i >= nums1.size() - 1) {
    			j = mid - i - 1;
    			if (size % 2 == 0) {
    				if (nums1[i] > nums2[j]) {
    					if (nums1[i] > nums2[j + 2]) {
    						return (nums2[j + 1] + nums2[j + 2]) / 2.0f;
    					}
    					else {
    						return (nums1[i] + nums2[j + 1]) / 2.0f;
    					}
    				}
    				else {
    					return (nums2[j] + nums2[j + 1]) / 2.0f;
    				}
    			}
    			else {
    				return (nums1[i] > nums2[j]) ? fmin(nums1[i], nums2[j + 1]) : nums2[j];
    			}
    		}
    		if (j >= nums2.size() - 1) {
    			i = mid - j - 1;
    			if (size % 2 == 0) {
    				if (nums2[j] > nums1[i]) {
    					if (nums2[j] > nums1[i + 2]) {
    						return (nums1[i + 1] + nums1[i + 2]) / 2.0f;
    					}
    					else {
    						return (nums2[j] + nums1[i + 1]) / 2.0f;
    					}
    				}
    				else {
    					return (nums1[i] + nums1[i + 1]) / 2.0f;
    				}
    			}
    			else {
    				return (nums2[j] > nums1[i]) ? fmin(nums2[j], nums1[i + 1]) : nums1[i];
    			}
    		}
    		if (nums1[i] > nums2[j]) {
    			j += 1;
    		}
    		else
    		{
    			i += 1;
    		}
    	}
    	if ((nums1.size() + nums2.size()) % 2 == 0) {
    		if (nums1[i] > nums2[j]) {
    			return (nums2[j] + fmin(nums1[i], j < nums2.size() - 1 ? nums2[j + 1] : INT_MAX)) / 2.0f;
    		}
    		else {
    			return (nums1[i] + fmin(nums2[j], i < nums1.size() - 1 ? nums1[i + 1] : INT_MAX)) / 2.0f;
    		}
    	}
    	else
    	{
    		return fmin(nums1[i], nums2[j]);
    	}
        }
    };
    

Log in to reply
 

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