Thursday, January 1, 2015

Merge Sorted Array (LeetCode Array)

Question: 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 (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Idea: Start from the end of A and B, copy the larger of A[i] and B[j] to the corresponding index (i+j+1) of A.

Time: O(n) Space: O(1)

Code:  
 public class Solution {  
   public void merge(int A[], int m, int B[], int n) {  
     int i=m-1;  
     int j=n-1;  
     while(i>=0||j>=0)  
     {  
       int v1=i<0?Integer.MIN_VALUE:A[i];  
       int v2=j<0?Integer.MIN_VALUE:B[j];  
       if(v1>=v2)  
         A[i+j+1]=A[i--];  
       else  
         A[i+j+1]=B[j--];  
     }  
   }  
 }  

No comments:

Post a Comment