Given two sorted integer arrays A and B, merge B into A as one sorted array.
1 // 时间复杂度 O(m+n),空间复杂度 O(1)
2 class Solution {
3 public:
4 void merge(int A[], int m, int B[], int n) {
5 int i=m-1,j=n-1,k=m+n-1;
6 while(i>=0&&j>=0)//从后面开始比较归并,直到有一个数组归并完
7 {
8 A[k--]=A[i]>B[j]?A[i--]:B[j--];//将大数赋给A[k]
9 }
10 while(j>=0)//若B还没归并完,直接归并到A
11 A[k--]=B[j--];
12 }
13 };