题目
合并两个排序的整数数组A和B变成一个新的数组。你可以假设A具有足够的空间(A数组的大小大于或等于m+n)去添加B中的元素。http://www.lintcode.com/zh-cn/problem/merge-sorted-array/
分析
既然A有足够的空间,那么只要把B中的元素归并到A中即可。由于A、B都是有序数组,通过两个游标,将B中的元素插入到A中,流程如下:
- 若A当前的游标指向的元素小于等于B,则A的游标向前滑动
- 若A当前的游标指向的元素大于B,则将A数组中从游标当前位置开始往后的元素全部向后移动一位,再将B数组中的游标指向元素拷贝到A的当前游标位置,同时A、B的游标向后移动
- 当B游标抵达数组末尾时,合并结束
- 有可能出现A的游标已经抵达末尾,但B的游标仍然未到末尾,此时直接将所有B中剩余元素逐一插入到A的游标位置
代码
class Solution {
void moveForward(int[] A, int start, int count){
for(;count >0 ; count--){
A[start+count] = A[start+count-1];
}
}
/**
* @param A: sorted integer array A which has m elements,
* but size of A is m+n
* @param B: sorted integer array B which has n elements
* @return: void
*/
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
// write your code here
int i = 0, j = 0;
int total = m;
for(;j < n && i < total;){
if(A[i] <= B[j]){
i++;
}else{
moveForward(A, i, total-i);
A[i++] = B[j++];
total++;
}
}
for( ; j < n ; ){
A[i++] = B[j++];
}
}
}