NC22 合并两个有序数组

二刷

不用考虑合并到最后A是否会被覆盖
不会
因为从后面开始弄 永远不会覆盖到A 被覆盖的都是已经排好序的 没用的

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){
            if(A[i] > B[j]){
                A[i+j+1] = A[i];
                i--;
            }
            else{
                A[i+j+1] = B[j];
                j--;
            }
        }
        while(j>=0) A[i+j+1] = B[j--]; 


    }
}

1.创造了一个新数组。

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int [] merge = new int[m+n];
        int i=0,j=0,k=0;
        while(i<m && j<n){ // 注意这里要是&& 我之前是 || 会出问题
            if(A[i]<B[j]){
                merge[k] = A[i];
                i++;
            }
            else{
                merge[k] = B[j];
                j++;
            }
            k++;
        }
        if(j==n){
            for(;i<m;k++,i++){
                merge[k] = A[i];
            }
        }
        if(i==m){
            for(;j<n;k++,j++){
                merge[k] = B[j];
            }
        }
        for(int count=0; count< m+n; count++ ){
            A[count] = merge[count];
        }
    }
}

2.因为给的题目已经扩充了 A 数组 因此 可以从 A数组屁股 从大到小进行排序， 这样节省空间。