Share my O(m+n) solution


  • 0
    X
    public double findMedianSortedArrays(int A[], int B[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int m = A.length - 1;
        int n = B.length - 1;
        while (m >= 0 && n >= 0) {
            if (A[m] > B[n]) {
                list.add(A[m--]);
            } else {
                list.add(B[n--]);
            }
        }
        while (m >= 0) {
            list.add(A[m--]);
        }
        while (n >= 0) {
            list.add(B[n--]);
        }
        return (list.get(list.size() >> 1) + list.get((list.size() - 1) >> 1)) / 2.0;
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 1
    C

    O(log(m + n)) requires more than classical merge sort.. only conqure and divide can give you log complexity


Log in to reply
 

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