Java Log(m+n) in LOOP


  • 0
    R

    public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {

        int indexA = -1, indexB = -1;
        int lengthBoth = A.length + B.length;
        // for calculate the result, we need get the number of items as this , even (2+2)/2+1=3 items, odd (2+3)/2+1 = 3 items
        int mid = (A.length + B.length) / 2 + 1;
        int[] twoMax = new int[2];
        if (A == null || A.length == 0) {
            return getMedianFromArray(B);
        }
        if (B == null || B.length == 0) {
            return getMedianFromArray(A);
        }
        // we remove the less section from one array, and record the removed index
        // if it is a odd, then we get the number at length BothLength/2+1, if it is even, then we get the number at BothLength/2 -1 and BothLength/2
    // so if we always add one when odd, the twoMax[0], will be the number when odd
        for (int appendA = mid / 2 + mid % 2,rest=mid; // if the bothLength is 3, then the expect appendA should be 1
             appendA > 0;
             rest=mid-(indexA + indexB + 2),appendA = (rest)/2 + rest % 2) {// append the value lost from the divide
            int diffB = appendA;
            if (indexA == A.length - 1) {
                indexB += rest;// when odd, we get BothLength/2 -1 and BothLength/2, so there we don't need plus one again
                break;
            }
            if (indexB == B.length - 1) {
                indexA += rest;
                break;
            }
            if (indexA + appendA > A.length - 1) {
                diffB = diffB + (appendA - (A.length - indexA - 1));
                appendA = A.length - 1 - indexA;
            }
            if (indexB + diffB > B.length - 1) {
                appendA = appendA + (diffB - (B.length - indexB - 1));
                diffB = B.length - 1 - indexB;
            }
            if (A[indexA + appendA] < B[indexB + diffB]) {
                indexA += appendA;
            } else {
                indexB += diffB;
            }
        }
        getTwoMaxValueFromTwoArrayIndex(A, B, indexA, indexB, twoMax);
        if (lengthBoth % 2 == 1) {
            return twoMax[0];
        } else {
            return (((double) twoMax[0] + (double) twoMax[1])) / 2.0;
        }
    }
    
    private static void getTwoMaxValueFromTwoArrayIndex(int[] A, int[] B, int indexA, int indexB, int[] result) {
        if(indexA<0){
            result[0]=B[indexB];
            if(indexB-1<0)
                result[1]=A[A.length-1];
            else
                result[1]=B[indexB-1];
            return ;
        }
        if(indexB<0){
            result[0]=A[indexA];
            if(indexA-1<0)
                result[1]=B[B.length-1];
            else
                result[1]=A[indexA-1];
            return;
        }
        if (A[indexA] > B[indexB]) {
            result[0] = A[indexA];
            if (indexA > 0) {
                result[1] = Math.max(A[indexA - 1], B[indexB]);
            } else {
                result[1] = B[indexB];
            }
        } else {
            result[0] = B[indexB];
            if (indexB > 0) {
                result[1] = Math.max(A[indexA], B[indexB - 1]);
            } else {
                result[1] = A[indexA];
            }
        }
    }
    
    private static double getMedianFromArray(int A[]) {
        if (A != null && A.length != 0) {
            if (A.length % 2 == 1) {
                return A[A.length / 2];
            } else {
                return ((double) A[A.length / 2 - 1] + (double) A[A.length / 2]) / 2;
            }
        } else {
            return 0;
        }
    }
    

    }


Log in to reply
 

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