题解 | #牛奶工厂# 归并

知识点

模拟 归并

思路

从后往前，归并两个数组，如果一个数组全用完了，就把剩下的接在后面就好了。时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param time1 int整型vector 
     * @param time2 int整型vector 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int milk_sum(vector<int>& time1, vector<int>& time2, int m, int n) {
        // 从后往前
        int idx = m + n - 1;
        int i = m - 1, j = n - 1;
        int res = 0;
        while (i >= 0 and j >= 0) {
            if (time1[i] >= time2[j]) {
                time1[idx] = time1[i --];
            }
            else {
                time1[idx] = time2[j --];
            }
            res += time1[idx --];
        }
        while (i >= 0) {
            time1[idx] = time1[i --];
            res += time1[idx --];
        }
        while (j >= 0) {
            time1[idx] = time2[j --];
            res += time1[idx --];
        }
        return res;
    }
};