NC22题解 | #合并两个有序的数组#

• 题目默认了升序?
• 3种方法
• 解法1：System.arraycopy()
• 解法2：定义一个新数组C，再利用双指针,从后往前遍历
• 解法3：直接利用数组A，三指针，此处需要证明指针p不会覆盖指针i，即A[p]不会覆盖A[i]

解法1:System.arraycopy()

    public void merge(int A[], int m, int B[], int n) {
        System.arraycopy(B,0,A,m,n);
        Arrays.sort(A);
    }

解法2:双指针，新数组

    //额外数组
    public void merge(int A[], int m, int B[], int n) {
        int[] C = new int[m+n];
        int k = m+n-1;
        int i = m-1, j = n-1;
        while(i >= 0 && j >= 0){
            C[k--] = A[i]>B[j]?A[i--]:B[j--];
        }
        while(j>=0){
            C[k--] = B[j--];
        }
        while(i>=0){
            C[k--] = A[i--];
        }
        System.arraycopy(C,0,A,0,m+n);
    }

解法3：3指针，原数组A

• 证明：A本身的值不会被新值p覆盖
  1. i是A的指针
  2. j是B的遍历指针
  3. p是结果指针
     • 假设A移动了a个值，则此时i = m-a;
     • 假设B移动了b个值，则此时j = n-b >=0;
     • 则此时p = m+n-(a+b) = (m-a)+(n-b) >= i;
     • 意味着p始终在i后面，A[p]不会覆盖原先的A[i]的值

    //原数组A
    //证明：A本身的值不会被新值p覆盖
    //假设A移动了a个值，则此时i = m-a;
    //假设B移动了b个值，则此时j = n-b >=0;
    //则此时p = m+n-(a+b) = (m-a)+(n-b) >= i;
    //意味着p始终在i后面，A[p]不会覆盖原先的A[i]的值
    public void merge(int A[], int m, int B[], int n) {
        int p = m+n-1;
        int i = m-1, j = n-1;
        while(i >= 0 && j >= 0){
            A[p--] = A[i]>B[j]?A[i--]:B[j--];
        }
        while(j>=0){
            A[p--] = B[j--];
        }
    }
}