首页 > 代码库 > [leetcode]_Merge Sorted Array

[leetcode]_Merge Sorted Array

2024-07-06 00:57:22   217人阅读

题目：合并两个有序数组A ， B，将合并后的数组存到A中。假设A的空间足够装下A和B所有的元素。

 

思路：这道题考虑如果正向扫描两个数组，则每插入一个元素，则需移动A后的所有元素。换个角度想，既然元素个数一定，则从尾部扫描两个数组，依次放入到A的尾部，这样既不会产生大量元素的移动，也不会造成A中元素被覆盖。很顺利~

 

代码：

 1 public void merge(int A[], int m, int B[], int n) {
 2         int start = m + n - 1;
 3         int i = m - 1,j = n - 1;
 4         while(i >= 0 && j >= 0){
 5             if(A[i] <= B[j]){
 6                 A[start--] = B[j--];
 7             }else{
 8                 A[start--] = A[i--];
 9             }
10         }
11         //不用考虑i >= 0的情况，如果i >= 0 , 则本身这些元素就应该放到A中去，即不用移动了。
12         while(j >= 0){
13             A[start--] = B[j--];
14         }
15     }

 


联系
我们