LintCode -- 合并排序数组 II

朴灿烈づ我的快乐病毒、 2022-05-25 11:12 176阅读 0赞

## 描述 ##

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

## 样例 ##

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

## 挑战 ##

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

## 原题地址 ##

[https://www.lintcode.com/problem/merge-two-sorted-arrays/][https_www.lintcode.com_problem_merge-two-sorted-arrays]

## 难度级别 ##

容易

## 解题思路 ##

这道题一看，怎么这么眼熟，这不就是归并吗？

public class Solution { 
        /** * @param A: sorted integer array A * @param B: sorted integer array B * @return: A new sorted integer array */
        public int[] mergeSortedArray(int[] A, int[] B) {
            int lena = A.length;
            int lenb = B.length;
            int[] merge = new int[lena + lenb];
            int i = 0, j = 0, k = 0;
            /*if (A[lena - 1] < B[0]) { for (k = 0; k < lena + lenb; k++) { if (k < lena) { merge[k] = A[i]; i++; } else { merge[k] = B[j]; j++; } } } else if (B[lenb - 1] < A[0]) { for (k = 0; k < lena + lenb; k++) { if (k < lenb) { merge[k] = B[i]; i++; } else { merge[k] = A[j]; j++; } } } else { 这段意义不大，会很大程度上影响性能*/
                while (i < lena && j < lenb) {
                    if (A[i] < B[j]) {
                        merge[k++] = A[i++];
                    } else {
                        merge[k++] = B[j++];
                    }
                }
                while (i < lena) {
                    merge[k++] = A[i++];
                }
                while (j < lenb) {
                    merge[k++] = B[j++];
                }
            }
            return merge;
        }
    }

[https_www.lintcode.com_problem_merge-two-sorted-arrays]: https://www.lintcode.com/problem/merge-two-sorted-arrays/