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

双指针

这题其实就是归并排序中的并部分，由于要在A[ ]上原地修改，所以使用一个临时数组temp[ ]来存放A数组中的元素，然后使用双指针比较，较小的元素放入A[ ]中即可

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        // 特殊情况
        if (n == 0) return;
        if (m == 0 && n == 0) return;
        // 先把A向后移动
        int start = 0;
        for (int i = 0; i < n; ++i) {
            start++;
        }
        int[] temp = new int[m];
        for (int i = 0; i < m; ++i) {
            temp[i] = A[i];
        }
        int pa = 0;
        int pb = 0;
        int cur = 0;
        while (pa < m && pb < n) {
            if (temp[pa] <= B[pb]) {
                A[cur] = temp[pa];
                pa++;
            } else { // temp[pa] > B[pb]
                A[cur] = B[pb];
                pb++;
            }
            cur++;
        }
        // 如果有一条链表还没有读完
        if (pa < m) { // 剩下的是pa
            for (; pa < m; pa++, cur++) {
                A[cur] = temp[pa];
            }
        }
        if (pb < n) { // 剩下的是pb
            for (; pb < n; pb++, cur++) {
                A[cur] = B[pb];
            }
        }
    }
}