写点什么

LeetCode 题解:2363. 合并相似的物品,双指针,详细注释

作者:Lee Chen
  • 2023-02-28
    福建
  • 本文字数:631 字

    阅读完需:约 2 分钟

LeetCode题解:2363. 合并相似的物品,双指针,详细注释

原题链接:https://leetcode.cn/problems/merge-similar-items/


解题思路:


  1. 先将两个数组排序

  2. 再用两个指针ij分别遍历两个数组的元素

  3. 如果items1[i][0] === items2[j][0],就将两个同价值的物品重量相加

  4. 如果items1[i][0] < items2[j][0],就存储items1[i]

  5. 如果items1[i][0] > items2[j][0],就存储items2[j]

  6. 还需要考虑指针移出数组的场景


/** * @param {number[][]} items1 * @param {number[][]} items2 * @return {number[][]} */var mergeSimilarItems = function (items1, items2) {  let result = []  // 先对两个数组进行排序  items1.sort((a, b) => a[0] - b[0])  items2.sort((a, b) => a[0] - b[0])
// 用两个指针分别合并数组 for (let i = 0, j = 0; i < items1.length || j < items2.length; ) { // 价值相同时,需要将两个重量相加 if (items1[i]?.[0] === items2[j]?.[0]) { result.push([items1[i][0], items1[i++][1] + items2[j++][1]]) } // 如果指针j已经移出items2,或者items1[i]的价值比items2[j]小,此时直接存储items1[i] else if (!items2[j] || items1[i]?.[0] < items2[j]?.[0]) { result.push(items1[i++]) } // 如果指针已经移出items1,或者items1[i]的价值比items2[j]大,此时直接存储items2[j] else if (!items1[i] || items1[i]?.[0] > items2[j]?.[0]) { result.push(items2[j++]) } }
return result}
复制代码


复杂度分析:


  • 时间复杂度:O(n+m)log⁡(n+m)

发布于: 刚刚阅读数: 4
用户头像

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:2363. 合并相似的物品,双指针,详细注释_JavaScript_Lee Chen_InfoQ写作社区