2363. 合并相似的物品

题目链接：2363. 合并相似的物品

方法一：归并

解题思路

先对两个整数数组进行\(sort\)排序，然后对两个数组进行归并操作。

代码

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        sort(items1.begin(), items1.end());
        sort(items2.begin(), items2.end());
        int i = 0, j = 0, n1 = items1.size(), n2 = items2.size();
        vector<vector<int>> ans;
        while (i < n1 && j < n2) {
            if (items1[i][0] == items2[j][0]) ans.push_back({items1[i][0], items1[i ++ ][1] + items2[j ++ ][1]});
            else if (items1[i][0] < items2[j][0]) ans.push_back(items1[i ++ ]);
            else ans.push_back(items2[j ++ ]);
        }
        while (i < n1) ans.push_back(items1[i ++ ]);
        while (j < n2) ans.push_back(items2[j ++ ]);
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(nlogn)\)；
空间复杂度：\(O(1)\)。

方法二：哈兮

解题思路

利用数组\(w\)存储\(value\)的\(weight\)的值，即\(w[value] = weight\)，需要消耗额外的存储空间；

代码

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        int w[1001] = {0}; // w[i]表示value = i时的weight的值
        for (auto &v : items1) w[v[0]] += v[1];
        for (auto &v : items2) w[v[0]] += v[1];
        vector<vector<int>> ans;
        for (int i = 0; i <= 1000; i ++ ) if (w[i]) ans.push_back({i, w[i]});
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n)\)，\(n = max(n1, n2, m)\)，\(n1\) 和 \(n2\)为数组长度，\(m\)为数组\(w\)的长度；
空间复杂度：\(O(m)\)。