Share My Java Solution


  • 0
    N

    This is my ac solution.I use another array,so the time complicity is O(n) and space complicity is O(n).

    public class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        	int tmp[] = new int[n+m];
        	int i=0 , j=0;
        	for(int k = 0;k<m+n;k++){
        		if(i==m) tmp[k] = nums2[j++];
        		else if(j==n) tmp[k] = nums1[i++];
        		else if(nums1[i]<nums2[j]){
        			tmp[k] = nums1[i++];
        		}else{
        			tmp[k] = nums2[j++];
        		}
        	}
        	int k = 0;
        	for(int num : tmp){
        		nums1[k++] = num;
        	}
        }
    }
    
    

    And there must be another more efficient method!When I see the others' method,I found it's a good idea to sort arry from bottom.The time complicity is O(n) and space complicity is O(1).

    public class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
    		int i = m-1,j = n-1;
    		for(int k=m+n-1;k>=0;k--){
    			if(i<0) nums1[k] = nums2[j--];
                          //When j<0,the nums1 is ordered!
    			else if(j<0) break;
    			else if(nums1[i]>nums2[j]) nums1[k] = nums1[i--];
    			else nums1[k] = nums2[j--];
    		}
        }
    }
    
    

Log in to reply
 

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