I did the log N median finding. Any way to improve my base case?


  • 0
    P
    I'm wondering how to improve the base case. is there an easier method than merging? I bet theres a hard coded base case, but that might be a little ugly.
    public class Solution {
            public double findMedianSortedArrays(int A[], int B[]) {
                if ((A == null || A.length == 0) && (B == null || B.length == 0))
                    return -1;
                if (A == null || A.length == 0)
                    return findMedianSortedArray(B, 0, B.length - 1);
                if (B == null || B.length == 0)
                    return findMedianSortedArray(A, 0, A.length - 1);
                return findMedianSortedArraysR(A, 0, A.length - 1, B, 0, B.length - 1);
            }
            public double findMedianSortedArraysR(int A[], int la, int ra, int B[], int lb, int rb) {
                if (ra - la + rb - lb < 2) {
                    return findMedianSortedArray(merge(A,B), 0, A.length + B.length - 1);
                }
                double medA = findMedianSortedArray(A, la, ra);
                double medB = findMedianSortedArray(B, lb, rb);
                if (medA < medB)
                    return findMedianSortedArraysR(A, (ra + la) / 2, ra, B, lb, (rb + lb) / 2);
                else
                    return findMedianSortedArraysR(A, la, (ra + la) / 2, B, (rb + lb) / 2, rb);
            }
            public double findMedianSortedArray(int A[], int l, int r) {
                if ((r - l + 1) % 2 == 0)
                    return (A[(r - l) / 2] + A[((r - l) / 2) + 1]) / 2.0;
                return A[(r - l) / 2];
            }
            public int[] merge(int[] A, int[] B) {
                int[] C = new int[A.length + B.length];
                int i = 0;
                int j = 0;
                int k = 0;
                while (j < A.length && k < B.length)
                    if (A[j] < B[k])
                        C[i++] = A[j++];
                    else
                        C[i++] = B[k++];
                while (j < A.length)
                    C[i++] = A[j++];
                while (k < B.length)
                    C[i++] = B[k++];
                return C;
            }
        }

  • 0
    A

    The function findMedianSortedArray is not working properly if the L is not 0.
    This code is only working because the base case is enough to solve the whole problem.
    check the second method in this link
    http://www.geeksforgeeks.org/median-of-two-sorted-arrays/


  • 0
    P

    The function findMedianSortedArray must be working correctly when L( I am assuming L = array length) is not 0 because it is called when one of the arrays is empty or null and the other has length more than 0, and Leetcode has test cases for this. This code passed all the test cases. Further I checked out the method from the link you gave, and I think it's cool to see the base case. However, I think my code is conceptually easier to understand because there are fewer if statements.


Log in to reply
 

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