Friday, September 27, 2013

Merge Sorted Array

Q:
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

A:

-----------------------2nd pass ---------------------------

public class Solution { 
    public void merge(int A[], int m, int B[], int n) {
        int iA = m-1,iB=n-1;
        while(iB>=0){
            if(iA>=0 && A[iA] > B[iB]){
                A[iA+iB+1] = A[iA];
                iA--;
            }else{
                A[iA+iB+1] = B[iB];
                iB--;
            }
        }
    }
}

-------------------1st pass----------------------------

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int pA = m-1;
        int pB = n-1;
        while( pB >= 0 && pA>=0){
            if(A[pA] >= B[pB] ){
                A[pA+pB+1] = A[pA];
                pA--;
            }else{
                A[pA+pB+1] = B[pB];
                pB--;
            }
        }
        // test if pA <0, then we copy the rest of B
        if(pB>=0){
            for(int i =pB;i>=0;i--){
                A[i]=B[i];
            }
        }
        
    }
}

No comments:

Post a Comment