Java AC by Merging Sort


  • 0
    L

    public class Solution {

    public double findMedianSortedArrays(int A[], int B[]) {
        if(A.length ==0){
            return B.length%2 == 0 ? ((double)B[B.length/2 -1] + (double)B[B.length/2])/2 : (double)B[B.length/2];
        }else if(B.length == 0){
             return A.length%2 == 0 ? ((double)A[A.length/2 -1] + (double)A[A.length/2])/2 :(double) A[A.length/2];
        }
        //Merging Sort
        int m = A.length,n = B.length;
        int[] S = new int[m + n];
        int i = 0, j=0,k=0;
        while(i < m && j < n){
            if(A[i] <= B[j]){
                S[k] = A[i];
                i++;k++;
            }else{
                S[k] = B[j];
                j++;k++;
            }
        }
        
        if(i == m){
            S = this.addArray(Arrays.copyOfRange(S, 0, k),Arrays.copyOfRange(B,j,n));
        }
        if(j == n){
           S = this.addArray(Arrays.copyOfRange(S, 0, k),Arrays.copyOfRange(A,i,m));
        }
        
        if((m+n)%2 == 0)
            return ((double)S[(m+n)/2-1] + (double) S[(m+n)/2])/2;
        else
            return (double)S[(m+n)/2];
    }
    
    private int[] addArray(int[] A,int[] B){
        int[] S = new int[A.length + B.length];
        for(int i=0;i<A.length;i++){
            S[i] = A[i];
        }
        for(int j=0,k=A.length;j<B.length;j++,k++){
            S[k] = B[j];
        }
        
        return S;
    }
    

    }


  • 0
    C

    This solution has O(N) computation complexity and need extra space. But it solved the problem. :)


Log in to reply
 

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