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

JustYY.com 小赖子的英国生活和资讯

6 years ago

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

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

复杂度是 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?

强烈推荐

英国代购-畅购英伦
TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
Quidco 返现 (也是很不错的英国返现网站, 返现率高)
注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
注册就送10美元, 免费使用2个月的阿里云主机(性价比超高, 每月只需4.5美元)
注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
刷了美国运通信用卡一年得到的积分换了 485英镑
注册就送50英镑 – 英国最便宜最划算的电气提供商
能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

强烈推荐

相关文章：