My 20ms C solution


  • 0
    M
    double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
        if(nums2Size < nums1Size) {
            return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);}
    
        int low = 0, high = nums2Size, count1 = 0, count2 = 0, mid = (nums1Size+nums2Size)/2 + 1; 
    
        int find_index_to_insert(int num, int *nums, int size) {
            int lo = 0, hi = size;
            while(lo != hi-1) {
                int index = (lo+hi) / 2;
                if(nums[index] >= num) {
                    hi = index;}
                else {
                    lo = index;}}
            return (nums[lo] > num) ? lo : lo+1;}
    
        while(count1 + count2 != mid) { // pick count1 elements from nums1 and count2 elements from nums2
            if(count1 == nums1Size) {
                count2 = mid - count1;
                break;}
            if(low == high) {
                count1 = mid - count2;
                break;}
            int index2 = (low+high) / 2;
            int index1 = find_index_to_insert(nums2[index2], nums1+count1, nums1Size-count1);
            if(count1+index1 + index2+1 > mid) {
                high = index2;}
            else {
                count1 += index1;
                low = count2 = index2+1;}}
    
        if((nums1Size+nums2Size) % 2 == 0) { // take care of all the cases
            if(count1 == 0) return ((double)nums2[count2-1]+nums2[count2-2])/2;
            if(count2 == 0) return ((double)nums1[count1-1]+nums1[count1-2])/2;
            int first, second;
            if(nums1[count1-1] > nums2[count2-1]) {
                first = nums1[count1-1];
                second = nums2[count2-1];}
            else {
                first = nums2[count2-1];
                second = nums1[count1-1];}
            if(count1 >= 2) {
                second = (second > nums1[count1-2]) ? second : nums1[count1-2];}
            if(count2 >= 2) {
                second = (second > nums2[count2-2]) ? second : nums2[count2-2];}
            return ((double)first+second)/2;}
        if(count1 == 0) return (double)nums2[count2-1];
        if(count2 == 0) return (double)nums1[count1-1];
    
        return (double)(nums2[count2-1] > nums1[count1-1] ? nums2[count2-1] : nums1[count1-1]);}

Log in to reply
 

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