"elegant" c solution....


  • 0
    W
    int max(int a, int b) {
        return a > b ? a : b;
    }
    
    int min(int a, int b) {
        return a < b ? a : b;
    }
    
    int helper(int a[], int m, int b[], int n, int k) {
        if (n == 0) {
            return a[k];
        }
        if (m == 0) {
            return b[k];
        }
        if (k == 1) {
            int ret = max(a[0], b[0]);
            if (m >= 2) {
                ret = min(ret, a[1]);
            }
            if (n >= 2) {
                ret = min(ret, b[1]);
            }
            return ret;
        }
        if (n == 1) {
            if (b[0] >= a[k]) {
                return a[k];
            } else {
                return max(b[0], a[k-1]);
            }
        }
        if (m == 1) {
            if (a[0] >= b[k]) {
                return b[k];
            } else {
                return max(a[0], b[k-1]);
            }
            
        }
        if (k >= (m + n) / 2) {
            // discard left half of a or b
            if (a[m/2] > b[n/2]) {
                return helper(a, m, b + n / 2, n - n / 2, k - n / 2);
            } else {
                return helper(a + m / 2, m - m / 2, b, n, k - m / 2);
            }
        } else {
            if (a[m/2] > b[n/2]) {
                return helper(a, m / 2, b, n, k);
            } else {
                return helper(a, m, b, n / 2, k);
            }
        }
    }
    
    double findMedianSortedArrays(int a[], int m, int b[], int n) {
        if ((m + n) & 1) {
            return helper(a, m, b, n, (m + n) / 2);
        } else {
            return ( helper(a, m, b, n, (m + n) / 2) + helper(a, m, b, n, (m + n) / 2 - 1) ) / 2.0;
        }
    }
    

    hehe, fuck this problem....


Log in to reply
 

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