合并相似的物品【LC2363】
给你两个二维整数数组
items1和items2，表示两个物品集合。每个数组items有以下特质：
items[i] = [valuei, weighti]其中valuei表示第i件物品的 价值 ，weighti表示第i件物品的 重量 。items中每件物品的价值都是 唯一的 。请你返回一个二维数组
ret，其中ret[i] = [valuei, weighti]，weighti是所有价值为valuei物品的 重量之和 。注意：
ret应该按价值 升序 排序后返回。
还有一门考试
TreeMap
- 思路：使用TreeMap存储item，键值为价值，value值为重量，按价值升序排序。最后将元素放入list中
- 实现
class Solution { public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) { TreeMap<Integer,Integer> map = new TreeMap<>(); for (int[] item : items1){ map.put(item[0], map.getOrDefault(item[0], 0) + item[1]); } for (int[] item : items2){ map.put(item[0], map.getOrDefault(item[0], 0) + item[1]); } List<List<Integer>> res = new ArrayList<>(); for (var node : map.entrySet()){ List<Integer> path = new ArrayList<>(); path.add(node.getKey()); path.add(node.getValue()); res.add(path); } return res; } }
复杂度
时间复杂度：O ( n l o g n + m l o g m )
空间复杂度：O ( n + m )
排序+双指针
- 思路：将数组按照升序排序后，使用双指针按顺序放入结果集中
- 实现
class Solution { public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) { Arrays.sort(items1, (o1, o2) -> o1[0] - o2[0]); Arrays.sort(items2, (o1, o2) -> o1[0] - o2[0]); List<List<Integer>> res = new ArrayList<>(); int i = 0, j = 0; int m = items1.length, n = items2.length; while (i < m || j < n){ if (j == n || ( i < m && items1[i][0] < items2[j][0])){ List<Integer> path = new ArrayList<>(); path.add(items1[i][0]); path.add(items1[i][1]); res.add(path); i++; }else if (i == m || (j < n && items1[i][0] > items2[j][0])){ List<Integer> path = new ArrayList<>(); path.add(items2[j][0]); path.add(items2[j][1]); res.add(path); j++; }else{ List<Integer> path = new ArrayList<>(); path.add(items1[i][0]); path.add(items2[j][1] + items1[i][1]); res.add(path); j++; i++; } } return res; } }
复杂度
- 时间复杂度：O ( n l o g n + m l o g m )
- 空间复杂度：O ( 1 )
