2363.合并相似的物品

1、题干

给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质：

• items[i] = [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ，weighti 表示第 i 件物品的 重量 。
• items 中每件物品的价值都是 唯一的 。

请你返回一个二维数组 ret，其中 ret[i] = [valuei, weighti]， weighti 是所有价值为 valuei 物品的 重量之和 。

注意：ret 应该按价值 升序 排序后返回。

 

示例 1：

输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出：[[1,6],[3,9],[4,5]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 5 ，总重量为 5 。
所以，我们返回 [[1,6],[3,9],[4,5]] 。

示例 2：

输入：items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
输出：[[1,4],[2,4],[3,4]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
所以，我们返回 [[1,4],[2,4],[3,4]] 。

示例 3：

输入：items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
输出：[[1,7],[2,4],[7,1]]
解释：
value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。
所以，我们返回 [[1,7],[2,4],[7,1]] 。

 

提示：

• 1 <= items1.length, items2.length <= 1000
• items1[i].length == items2[i].length == 2
• 1 <= valuei, weighti <= 1000
• items1 中每个 valuei 都是 唯一的 。
• items2 中每个 valuei 都是 唯一的 。

2、思路1-整合+排序

整合两个数组再统一升序排序，接着遍历所有物品得到结果

3、代码

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    items1.push(...items2);
    items1.sort((a, b) => a[0] - b[0]);

    const ans = [];
    for (let i = 0; i < items1.length; i++) {
        if (items1[i][0] === items1[i + 1]?.at(0)) items1[i + 1][1] += items1[i][1];
        else ans.push(items1[i]);
    }

    return ans;
};

4、复杂度

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

5、执行结果

---

6、思路2-桶排序

以价值作为桶序号，累加物品重量，最后返回重量大于0的桶序号及其重量

桶内不需要再排序，而是累加数值，跟常见的桶排序有点不同

7、代码

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    const bucket = new Array(1001).fill(0);
    for (let i = 0; i < items1.length || i < items2.length; i++) {
        if (items1[i]) bucket[items1[i][0]] += items1[i][1];
        if (items2[i]) bucket[items2[i][0]] += items2[i][1];
    }

    return bucket.map((w, i) => [i, w]).filter(b => b[1]);
};

8、复杂度

• 时间复杂度：$O(max(C,n))$
• 空间复杂度：$O(C)$

9、执行结果

---

10、思路3-哈希+排序

以价值作为哈希表的键，累加物品重量，最后返回按键升序排序的键值对

11、代码

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    const map = new Map();
    for (let i = 0; i < items1.length || i < items2.length; i++) {
        if (items1[i]) map.set(items1[i][0], (map.get(items1[i][0]) || 0) + items1[i][1]);
        if (items2[i]) map.set(items2[i][0], (map.get(items2[i][0]) || 0) + items2[i][1]);
    }

    return [...map].sort((a, b) => a[0] - b[0]);
};

12、复杂度

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

13、执行结果

---

14、思路4-双指针+排序

先对两个数组分别排序，再使用双指针按价值从小到大遍历所有物品

15、代码

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    items1.sort((a, b) => a[0] - b[0]);
    items2.sort((a, b) => a[0] - b[0]);

    const ans = [];
    for (let i = 0, j = 0; i < items1.length || j < items2.length;) {
        while (i < items1.length && (!items2[j] || items1[i][0] < items2[j][0])) {
            ans.push(items1[i]);
            i++;
        }

        while (j < items2.length && (!items1[i] || items1[i][0] > items2[j][0])) {
            ans.push(items2[j]);
            j++;
        }

        if (i < items1.length && j < items2.length && items1[i][0] === items2[j][0]) {
            items1[i][1] += items2[j][1];
            ans.push(items1[i]);
            i++, j++;
        }
    }

    return ans;
};

16、复杂度

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(\log n)$

17、执行结果