6.Merge Two Sorted Arrays-合并排序数组（容易题）

合并排序数组

题目

合并两个排序的整数数组A和B变成一个新的数组。

样例

给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]

挑战

你能否优化你的算法,如果其中一个数组很大而另一个数组很小?

题解

双指针法，从后往前依次往新数组中添加两个指针指向的较大的数字。

class Solution { /** * @param A and B: sorted integer array A and B. * @return: A new sorted integer array */ public int[] mergeSortedArray(int[] A, int[] B) { int i = A.length - 1; int j=B.length - 1; int index = i + j + 1; int[] result = new int[index + 1]; while (i >= 0 && j >= 0) { if (A[i] > B[j]) { result[index--] = A[i--]; } else { result[index--] = B[j--]; } } while (i >= 0) { result[index--] = A[i--]; } while (j >= 0) { result[index--] = B[j--]; } return result; } }

Last Update 2016.8.15