数组合并

合并两个升序数组A和B到数组A

题目 给出两个有序的整数数组A(长度m)和B(长度n) ,请将AB数组合并到数组A中,变成一个有序的数组。 算法思路 合并后数据总长度m+n,最后一个元素的位置为A[m+n-1] 从前(下标0)向后(下标m-1,n-1)合并需要挪动后续元素,复杂度高。因此,我们从后向前合并。 如何合并?初始化当前合并下标lastPos = m+n-1, 当前A数组下标posA = m-1, 当前B数组下标posB = n-1 逐个比大小,A[posA]和B[posB]取较大元素,放入A[lastPos]。取A数组,则posA--; 取B数组则posB--。同时lastPos-- 最后如果B数组有剩余,填入A数组即可 关于4和5,如果想问为什么这样就可以达到目的。注意观察,原始A数组中特定位置的数据,要么保持原位不变,要么会向后移动。因此,我们只需要取最大元素,放入lastPos即可 代码实现 public class Solution { public void merge(int A[], int m, int B[], int n) { int posA = m-1; int posB = n-1; int lastPos = m + n - 1; while(posA >= 0 && p...
执行时间: 31.378984451294 毫秒