Merge Sorted Array

问题描述

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

算法

代码一

 1 public void merge(int[] nums1,int m,int[]nums2,int n){
 2         for(int i=m-1;i>=0;i--){
 3             nums1[i+n]=nums1[i];
 4         }
 5         int i=n,j=0,k=0;
 6         while(i<n+m&&j<n){
 7             if(nums1[i]<=nums2[j]){
 8                 nums1[k]=nums1[i];
 9                 i++;
10             }else{
11                 nums1[k]=nums2[j];
12                 j++;
13             }
14             k++;
15         }
16         if(i>=n+m){
17             while(k<m+n){
18                 nums1[k]=nums2[j];
19                 k++;
20                 j++;
21             }
22         }else{
23             while(k<m+n){
24                 nums1[k]=nums1[i];
25                 i++;
26                 k++;
27             }    
28         }
29     }

代码二

 1 public void merge1(int[] nums1,int m,int[] nums2,int n){
 2         int i=m-1,j=n-1,k=m+n-1;
 3         while(i>=0&&j>=0){
 4             if(nums1[i]>=nums2[j]){
 5                 nums1[k--]=nums1[i--];
 6             }else{
 7                 nums1[k--]=nums2[j--];
 8             }
 9         }
10         while(j>=0){
11             nums1[k--]=nums2[j--];
12         }
13     }

注意事项

（1）数组的后移要从后边开始，而不是从前边开始。