Share my C++ solution


  • 1
    class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
    
            if (m > n) {
                return findMedianSortedArrays(B, n, A, m);
            }
    
            int i = m / 2;
            int j = n / 2;
            int k = 0;
            if (A[i] <= B[j]) { 
                if (m % 2 ==0) { k = min(i-1, n-j-1); }
                else { k = min(i, n-j-1); }
            } else {
                if (m % 2 ==0) { k = min(m-i-1, j-1); }
                else { k = min(m-i-1, j); }
            }
    
            
            if (m == 0) {
                return (n % 2 == 0) ? (B[j-1] + B[j])/2.0 : B[j];
            }
    
            if (m == 1) {
                if (n == 1) { return (A[0]+B[0])/2.0; }
                else if (n % 2 == 0) { return medianOfThree(A[0], B[j-1], B[j]); }
                else { return medianOfFour(A[0], B[j-1], B[j], B[j+1]); }
            }
    
            if (m == 2) {
                if (n == 2) { return medianOfFour(A[0], A[1], B[0], B[1]); }
                else if (n % 2 == 0) { return medianOfFour(max(A[1],B[j-2]), B[j-1], B[j], min(A[0], B[j+1])); }
                else { return medianOfThree(max(A[1],B[j-1]), B[j], min(A[0], B[j+1])); }  
            }
    
    
            if (A[i] <= B[j]) {
                return findMedianSortedArrays(A+k, m-k, B, n-k);
            } else  {
                return findMedianSortedArrays(A, m-k, B+k, n-k);
            } 
        }
    
    private:
        double medianOfThree(int a, int b, int c) {
            int maxI = max(max(a, b), c);
            int minI = min(min(a, b), c);
            return ( a + b + c - maxI - minI);
        }     
        double medianOfFour(int a, int b, int c, int d) {
            int maxI = max(max(max(a, b), c), d);
            int minI = min(min(min(a, b), c), d);
            return (a + b + c + d - maxI - minI) / 2.0;
        }
    };

Log in to reply
 

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