My O(m + n) time O(1) space cpp code similar to mergesort


  • 0
    Y
    class Solution {
    public:
    	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    		int a = nums1.size(), b = nums2.size();
    		if (a == 0 && b == 0)	return 0;
    		int count = 0, target = (a + b) / 2;
    		int i = 0, j = 0, curnum;
    		if (a == 0)	curnum = nums2[target - 1];
    		if (b == 0)	curnum = nums1[target - 1];
    		while (i < a && j < b) {
    			if (nums1[i] < nums2[j]) {
    				curnum = nums1[i];
    				i++;
    			}
    			else {
    				curnum = nums2[j];
    				j++;
    			}
    			count++;
    			if (count == target)
    				break;
    		}
    		int nextnum;
    
    		if (i == a) {
    			curnum = target > count ? nums2[target - count + j - 1] : curnum;
    			nextnum = nums2[target - count + j];
    		}
    		else if (j == b ) {
    			curnum = target > count ? nums1[target - count + i - 1] : curnum;
    			nextnum = nums1[target - count + i];
    		}
    		else
    			nextnum = min(nums1[i], nums2[j]);
    		
    		return (a + b) & 1 ? nextnum : (curnum + nextnum) / 2.0;
    
    	}
    };
    

Log in to reply
 

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