跳转至

88.合并两个有序数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //优先对数组nums1进行移动，要进行倒序移动否则例如[1,2,3,0]，
        //正序移动0移动到1会覆盖1的数据。
        for(int i = m -1;i >= 0;i--){
            nums1[i + n] = nums1[i];
        }
        int i = 0; //视为一个新的数组的索引
        int i1 = n; //数组nums1的索引
        int i2 = 0; //数组nums2的索引
        while(i1 < m + n || i2 < n){
            //有两种情况取nums1的值
            //1.当nums1的数据取完并且nums2中还有元素时
            //2.当两个数组都有元素并且 nums1[i1] < nums2[i2]
            if(i1 < m + n && (i2 >= n ||( i2 < n && nums1[i1] < nums2[i2]))){
                nums1[i] = nums1[i1];
                i1++;
            }else{
               nums1[i] = nums2[i2];
                i2++;  
            }
            i++;
        }
    }
}

如果倒序先把最大的放到末尾可以不用移位。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m -1; 
        int j = n -1; 
        int k = m + n -1;
        while(i > -1 || j > -1){
            if(i > -1 && (j <= -1 ||( j > -1 && nums1[i] > nums2[j]))){
                nums1[k] = nums1[i];
                i--;
            }else{
               nums1[k] = nums2[j];
                j--;  
            }
            k--;
        }
    }
}

优化代码

1
2
3
4
5
6
7
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m -1,j = n -1, k = m + n -1;
        while(i > -1 || j > -1)
           nums1[k--]= (i > -1 && (j <= -1 ||( j > -1 && nums1[i] > nums2[j]))) ? nums1[i--]: nums2[j--];    
    }
}