编程练习题 - 如何合并两个有序的数组？

题意: 合并两个已经排序好的数组. 这也是合并排序的最后一步操作. 还算比较简单的, 你可以从数组的两端开始. 一般来说从小到大合并会比较直观.

我们需要定义指向两个数组的下标, 每次循环就把比较小的那个数字添加到结果中即可. 当其中一个数组已经全部添加完后只需要把另一个数组剩下的元素依次添加到结果中即可.

复杂度是 O(A+B) , 其中A, B分别是两个数组的长度.

class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        vector<int> r;
        auto a = A.size();
        auto b = B.size();
        r.reserve(a + b);
        auto i = 0, j = 0;
        while (i < a && j < b) {
            if (A[i] < B[j]) { // take the smaller one
                r.push_back(A[i ++]);
            } else {
                r.push_back(B[j ++]);
            }
        }
        // push the remaining elements to sorted array.
        for (auto k = i ; k < a; ++ k) {
            r.push_back(A[k]);
        }
        for (auto k = j ; k < b; ++ k) {
            r.push_back(B[k]);
        }
        return r;
    }
};

class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        vector<int> r;
        auto a = A.size();
        auto b = B.size();
        r.reserve(a + b);
        auto i = 0, j = 0;
        while (i < a && j < b) {
            if (A[i] < B[j]) { // take the smaller one
                r.push_back(A[i ++]);
            } else {
                r.push_back(B[j ++]);
            }
        }
        // push the remaining elements to sorted array.
        for (auto k = i ; k < a; ++ k) {
            r.push_back(A[k]);
        }
        for (auto k = j ; k < b; ++ k) {
            r.push_back(B[k]);
        }
        return r;
    }
};

英文: Coding Exercise – How to Merge Two Sorted Array?

GD Star Rating
loading...

本文一共 155 个汉字, 你数一下对不对.

编程练习题 – 如何合并两个有序的数组?. (AMP 移动加速版本)
上一篇: PHP 是最好的语言, 但是......
下一篇: 谷歌的扔鸡蛋问题

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

小赖子的英国生活和资讯

编程练习题 – 如何合并两个有序的数组?

评论

相关文章：

评论