合并排序的数组

题目链接

合并排序的数组

题目描述

注意点

• A的末端有足够的缓冲空间容纳B
• A和B都是排序的

解答思路

• 最初想到的是双指针，从小到大找到合并B时应该A相应位置应该插入的元素，因为在插入的过程中B的元素会替换A原有位置的元素，所以需要先将A中的元素赋值到C，再双指针根据B和C对应的元素值大小插入到A中
• 参照题解，因为A的末端有足够的缓冲空间容纳B，所以可以使用逆向双指针，先把更大的元素插入到A中，就不需要额外的空间存储A中的元素了

代码

class Solution {public void merge(int[] A, int m, int[] B, int n) {int idxA = m - 1;int idxB = n - 1;while (idxA >= 0 || idxB >= 0) {if (idxA < 0) {A[idxA + idxB + 1] = B[idxB];idxB--;continue;}if (idxB < 0) {A[idxA + idxB + 1] = A[idxA];idxA--;continue;}if (A[idxA] > B[idxB]) {A[idxA + idxB + 1] = A[idxA];idxA--;} else {A[idxA + idxB + 1] = B[idxB];idxB--;}}}
}

关键点

• 双指针的思想