Share O(log(n)*log(m)) C++ code, can it be cleaner?


  • 0
    W
    class Solution {
    public:
        int lowerb(int A[], int n, int key) {
            int t = lower_bound(A, A+n-1, key) - A;
            if (A[t] < key) ++t;
            return t;
        }
        int upperb(int A[], int n, int key) {
            int t = upper_bound(A, A+n-1, key) - A;
            if (A[t] <= key) ++t;
            return t;
        }
        int findKth(int A[], int m, int B[], int n, int k) {
            if (!m&&!n) return 0;
            if (!m) return B[k-1];
            if (!n) return A[k-1];
            
            // assumen in A[0...m-1]
            if(!n) return A[k-1];
            int lo = 0, hi = m, mid;
    
            while(lo <= hi) {
                mid = lo + (hi - lo) / 2;
                int lower = lowerb(B, n, A[mid]) + lowerb(A, m, A[mid]) + 1;
                int upper = upperb(B, n, A[mid]) + upperb(A, m, A[mid]) ;
    
                if (k < lower) {
                    hi = mid - 1;
                } else if (k > upper) {
                    lo = mid + 1;
                } else {
                    return A[mid];
                }
            }
            // if not find
            return findKth(B, n, A, m, k);
        }
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            if ((m-n)%2) return findKth(A, m, B, n, (m+n)/2+1);
            return (findKth(A, m, B, n, (m+n)/2+1) + findKth(A, m, B, n, (m+n)/2)) * 0.5;
        }
    };

Log in to reply
 

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