数组指针 color http zh-cn code for 一个 amp
题目: 将两个排序好的数组组成一个新的排序好的数组, 给出 A=[1,2,3,4],B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]
你能否优化你的算法,如果其中一个数组很大而另一个数组很小?
思路: 两根指针分别指向两个数组的开头, 每次取值两个指针位置较小的数,指针后移, 直到其中一个数组结束, 将另外一个数组指针后面的元素连接到新数组的后面即可
关于挑战的情况 如果 A[0]>B[B.length-1]||A[A.length-1]<B[0] ,可根据情况 直接将 A 连接到 B 的后面 (或者 B 连接到 A 的后面)
代码如下
- public int[] mergeSortedArray(int[] A, int[] B) {
- int i = 0;
- int j = 0;
- int res[] = new int[A.length + B.length];
- int k = 0;
- while (i < A.length && j < B.length) {
- if (A[i] <= B[j]) {
- res[k++] = A[i++];
- } else {
- res[k++] = B[j++];
- }
- }
- if (i != A.length) {
- for (int a = i; a < A.length; a++) {
- res[k++] = A[a];
- }
- } else {
- for (int b = j; b < B.length; b++) {
- res[k++] = B[b];
- }
- }
- return res;
- }
- }
Java 合并两个排序数组
来源: http://www.bubuko.com/infodetail-2274832.html