描述
合并两个排序的整数数组 A 和 B 变成一个新的数组。
原地修改数组 A 把数组 B 合并到数组 A 的后面。
样例 1：
输入：
A = [1,2,3]
m = 3
B = [4,5]
n = 2输出：
[1,2,3,4,5]解释：
经过合并新的数组为[1,2,3,4,5]
样例 2：
输入：
A = [1,2,5]
m = 3
B = [3,4]
n = 2输出：
[1,2,3,4,5]解释：
经过合并新的数组为[1,2,3,4,5]
思路:题目中要求原地排序,则不能从新建一个数组用来记录A数组和B数组的比值并写入
应该采用双指针，从后往前原地合并
1.设置三个指针：
| 指针 | 说明 |
|---|---|
rightA = m - 1 | 指向 A 有效部分的最后一个元素 |
rightB = n - 1 | 指向 B 的最后一个元素 |
totalRight = m + n - 1 | 指向 A 的最末尾（即最终要放入数据的位置） |
2.从后往前比较 A 和 B 的元素：
每次从 A[rightA] 和 B[rightB] 中选出较大的放到 A[totalRight]；
比较完之后，移动对应的指针和 totalRight；
这样可以确保最大值先放到最右边，避免覆盖 A 的已有值。
3.如果 B 还有剩余，继续把 B 的元素复制到 A 的前面；
A 剩下的不用管，因为已经在合适位置上。
代码如下:
public class Solution {
public int[] mergeSortedArray(int[] A, int m, int[] B, int n) {
int rightA=m-1;
int rightB=n-1;
int totalright=m+n-1;
while(rightA>=0&&rightB>=0&&totalright>=0)
{
if(A[rightA]>=B[rightB])
{
A[totalright--]=A[rightA--];
}else
{
A[totalright--]=B[rightB--];
}
}
while(rightA>=0&&totalright>=0)
{
A[totalright--]=A[rightA--];
}
while(rightB>=0&&totalright>=0)
{
A[totalright--]=B[rightB--];
}
return A;
}
}
