20ms c solution


  • 0
    W
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
        if (nums1Size < 3 || nums2Size < 3) {
            int paritySize2 = nums2Size%2;
            if (nums1Size==0) {
                if (nums2Size==0)
                    return 0;
                if (paritySize2)
                    return nums2[nums2Size/2];
                return ((double)nums2[nums2Size/2-1] + (double)nums2[nums2Size/2])/2;
            }
            if (nums1Size>nums2Size)
                return findMedianSortedArrays(nums2,nums2Size,nums1,nums1Size);
    
            if (nums1Size==2) {
                if (nums2[nums2Size/2-1+paritySize2]>nums1[1])
                    return findMedianSortedArrays(nums1+1,1,nums2,nums2Size-1);
                if (nums2[nums2Size/2]<nums1[0])
                    return findMedianSortedArrays(nums1,1,nums2+1,nums2Size-1);
                if (nums2Size==2) {
                    if (nums1[0]<nums2[0] && nums1[1]<nums2[1])
                        return ((double)nums1[1] + (double)nums2[0])/2;
                    if (nums1[0]>nums2[0] && nums1[1]>nums2[1])
                        return ((double)nums1[0] + (double)nums2[1])/2;
                    if (nums1[0]>=nums2[0] && nums1[1]<=nums2[1])
                        return ((double)nums1[0] + (double)nums1[1])/2;
                    return ((double)nums2[0] + (double)nums2[1])/2;
                }
                return findMedianSortedArrays(nums1,2,nums2+nums2Size/2-1+paritySize2,2-paritySize2);
            } else if (nums1Size==1) {
                if (nums2Size==1)
                    return ((double)nums1[0] + (double)nums2[0])/2;
                if (nums2[nums2Size/2-1]>nums1[0])
                    return findMedianSortedArrays(nums1,0,nums2,nums2Size-1);
                if (nums2[nums2Size/2+paritySize2]<nums1[0])
                    return findMedianSortedArrays(nums1,0,nums2+1,nums2Size-1);
                return findMedianSortedArrays(nums1,1,nums2+nums2Size/2,paritySize2);
            }
        }
        
        int paritySize1 = nums1Size%2, paritySize2 = nums2Size%2;
        int middleIndex1,middleIndex2 = nums2Size/2;
        if (paritySize1==0 && paritySize2==0)
            middleIndex1 = nums1Size/2-1;
        else if (paritySize1==1 && paritySize2==1)
            middleIndex1 = nums1Size/2;
        else if (paritySize1==0)
            middleIndex1 = nums1Size/2-1;
        else
            middleIndex1 = nums1Size/2, middleIndex2 -= 1;
    
        if (nums1[middleIndex1] > nums2[middleIndex2]) {
            int delNums1 = nums1Size-1-middleIndex1, delNums2 = middleIndex2;
            int delNums = delNums1>delNums2?delNums2:delNums1;
            return findMedianSortedArrays(nums1,nums1Size-delNums,nums2+delNums,nums2Size-delNums);
        } else if (nums1[middleIndex1] < nums2[middleIndex2]) {
            int delNums1 = middleIndex1, delNums2 = nums2Size-1-middleIndex2;
            int delNums = delNums1>delNums2?delNums2:delNums1;
            return findMedianSortedArrays(nums1+delNums,nums1Size-delNums,nums2,nums2Size-delNums);
        } else {
            return nums1[middleIndex1];
        }
    
    }

Log in to reply
 

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