Share a none-recursive O(m+n) C code solution


  • -1
    R
    double findK(int * nums1, int nums1Size, int *nums2, int nums2Size, int k)
    
    {   
      int tmp; 
    int s1, s2;
    int idx1=0, idx2=0;
    int size1, size2;
    int inc1, inc2;
    size1 = nums1Size;
    size2 = nums2Size;
    s1 = 0;
    s2 = 0;
    
    
    while (1)
    {
    	if (size1 == 0)
    	{
    		return nums2[s2+k-1];
    	}
    	if (size2 == 0)
    	{
    		return nums1[s1+k-1];
    	}
    	if (k == 1)
    	{
    		return nums1[s1]<nums2[s2] ? nums1[s1] : nums2[s2];
    	}
    	if (k == 2)
    	{
    		if (nums1[s1] > nums2[s2])
    		{
    			//if (s2 + 1 <= nums2Size - 1)
    			if (s2 + 2 <= nums2Size )
    				return nums1[s1] < nums2[s2 + 1] ? nums1[s1] : nums2[s2 + 1];
    			else
    				return nums1[s1];
    		}
    		else if (nums1[s1] < nums2[s2])
    		{
    			//if (s1 + 1 <= nums1Size - 1)
    			if (s1 + 2 <= nums1Size)
    				return nums2[s2] < nums1[s1 + 1] ? nums2[s2] : nums1[s1 + 1];
    			else
    				return nums2[s2];
    		}
    		else
    			return nums1[s1];
    	}
    	tmp = (k>>1)-1;
    
    	if (size1 > tmp)
    	{
    		inc1 = tmp;
    	}
    	else
    		inc1 = size1 - 1;
    	if (size2 > tmp)
    	{
    		inc2 = tmp;
    	}
    	else
    		inc2 = size2 - 1;
    	idx1 = s1 + inc1;
    	idx2 = s2 + inc2;
    
    	if (nums1[idx1] == nums2[idx2])
    	{
    		if ((k-inc1-inc2) <= 1)
    			return nums1[idx1];
    		else
    		{
    			k = k - (inc1 + inc2+2);
    			s1 = s1 + inc1+1;
    			s2 = s2 + inc2+1;
    			size1 = size1 - inc1-1;
    			size2 = size2 - inc2-1;
    			if (k == 0)
    				return nums2[idx2];
    		}
    	}
    	else if (nums1[idx1] > nums2[idx2])
    	{
    		k = k - inc2 - 1;
    		if (k == 0)
    			return nums2[idx2];
    		s2 = idx2+ 1;
    		size2 = size2 - (inc2 + 1);
    	}
    	else
    	{
    		k = k - inc1 - 1;
    		if (k == 0)
    			return nums1[idx1];
    		s1 = idx1+ 1;
    		size1 = size1 - (inc1 + 1);
    	}
    }
    }
    
    
    
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int m = nums1Size;
    int n = nums2Size;
    int t = (m + n) / 2;
    if ((n + m) % 2)
    	return findK(nums1, nums1Size, nums2, nums2Size, ((n +m+1) >> 1));
    else
    	return ((findK(nums1, nums1Size, nums2, nums2Size, (n + m) >> 1) + findK(nums1, nums1Size, nums2, nums2Size, ((n + m ) >> 1)+1)) / 2.0);
    

    }


Log in to reply
 

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