哈希表 + 键名自动排序，哈希表 + 升序排列，二分查找实现插入排序 3 方法求解《2363. 合并相似的物品》
例题
给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质：
items[i] = [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ，weighti 表示第 i 件物品的 重量 。
items 中每件物品的价值都是 唯一的 。
请你返回一个二维数组 ret，其中 ret[i] = [valuei, weighti]， weighti 是所有价值为 valuei 物品的 重量之和 。
注意：ret 应该按价值 升序 排序后返回。
答案
哈希表 · 自动排序
var mergeSimilarItems = function(items1, items2) {
const h = Object.create(null)
const m = items1.length, n = items2.length
for (let i = 0; i < m; i++) {
h[items1[i][0]] = items1[i][1]
}
for (let i = 0; i < n; i++) {
h[items2[i][0]] = (h[items2[i][0]] || 0) + items2[i][1]
}
return Object.entries(h)
};哈希表 · 升序排列
function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
const m = items1.length, n = items2.length
const h = new Map
for (let i = 0; i < (m + n); i++) {
if (i < m) h.set(items1[i][0], items1[i][1])
if (i >= m) h.set(items2[i - m][0], (h.get(items2[i - m][0]) || 0) + items2[i - m][1])
}
return Array.from(h.entries()).sort((a, b) => a[0] - b[0])
};func mergeSimilarItems(items1 [][]int, items2 [][]int) [][]int {
h := map[int]int{}
for _, item := range items1 {
h[item[0]] = item[1]
}
for _, item := range items2 {
h[item[0]] += item[1]
}
ans := [][]int{}
for key, val := range h {
ans = append(ans, []int{key, val})
}
sort.Slice(ans, func(i, j int) bool {
return ans[i][0] < ans[j][0]
})
return ans
}class Solution {
function mergeSimilarItems($items1, $items2) {
$h = array();
foreach ($items1 as $item) {
$h[$item[0]] = $item[1];
}
foreach ($items2 as $item) {
$h[$item[0]] += $item[1];
}
$ans = [];
foreach ($h as $key => $val) $ans []= [$key, $val];
usort($ans, fn($a, $b) => $a[0] > $b[0]);
return $ans;
}
}class Solution {
public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
Map<Integer, Integer> h = new HashMap<Integer, Integer>();
for (int[] item : items1) {
h.put(item[0], item[1]);
}
for (int[] item : items2) {
h.put(item[0], h.getOrDefault(item[0], 0) + item[1]);
}
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for (Map.Entry<Integer, Integer> entry : h.entrySet()) {
List<Integer> pair = new ArrayList<Integer>();
pair.add(entry.getKey());
pair.add(entry.getValue());
ans.add(pair);
}
Collections.sort(ans, (a, b) -> a.get(0) - b.get(0));
return ans;
}
}public class Solution {
public IList<IList<int>> MergeSimilarItems(int[][] items1, int[][] items2) {
IDictionary<int, int> h = new Dictionary<int, int>();
foreach (int[] item in items1) {
h.Add(item[0], item[1]);
}
foreach (int[] item in items2) {
if (h.ContainsKey(item[0])) h[item[0]] += item[1];
else h.Add(item[0], item[1]);
}
IList<IList<int>> ans = new List<IList<int>>();
foreach (KeyValuePair<int, int> pair in h) {
ans.Add(new List<int>{pair.Key, pair.Value});
}
((List<IList<int>>) ans).Sort((a, b) => a[0] - b[0]);
return ans;
}
}class Solution {
public:
vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
unordered_map<int, int> h;
for (vector<int> &item : items1) {
h[item[0]] = item[1];
}
for (vector<int> &item : items2) {
h[item[0]] += item[1];
}
vector<vector<int>> ans;
for (auto &[key, value] : h) {
ans.push_back({key, value});
}
sort(ans.begin(), ans.end());
return ans;
}
};class Solution:
def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
m = dict()
for key, val in items1: m[key] = val
for key, val in items2: m[key] = m.get(key, 0) + val
return sorted([a, b] for a, b in m.items())插入排序 · 二分查找 · lower_bound
function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
const m = items1.length, n = items2.length, r = []
for (let i = 0; i < (m + n); i++) {
if (i < m) insert(r, items1[i])
if (i >= m) insert(r, items2[i - m])
}
return r
};
function insert(nums: number[][], numAr: number[]) {
const index = lower_bound(nums, numAr)
if (nums[index] !== void 0 && nums[index][0] === numAr[0]) nums[index][1] += numAr[1]
else nums.splice(index, 0, numAr)
}
function lower_bound(nums: number[][], target: number[]) {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m][0] >= target[0]) r = m - 1
else l = m + 1
}
return l
}int lower_bound(int** nums, int* target, int numsSize) {
int l = 0, r = numsSize - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m][0] >= target[0]) r = m - 1;
else l = m + 1;
}
return l;
}
int insert(int** nums, int* num, int numsSize) {
int index = lower_bound(nums, num, numsSize);
if (index < numsSize && nums[index][0] == num[0]) nums[index][1] += num[1];
else {
int* pair = malloc(sizeof(int) * 2);
nums[numsSize] = pair;
int i = numsSize;
while (i > index) {
nums[i][0] = nums[i - 1][0];
nums[i][1] = nums[i - 1][1];
i--;
}
nums[index][0] = num[0];
nums[index][1] = num[1];
numsSize++;
}
return numsSize;
}
int** mergeSimilarItems(int** items1, int items1Size, int* items1ColSize, int** items2, int items2Size, int* items2ColSize, int* returnSize, int** returnColumnSizes){
int** res = malloc(sizeof(int*) * (items1Size + items2Size));
int numsSize = 0;
for (int i = 0; i < items1Size; i++) {
numsSize = insert(res, items1[i], numsSize);
}
for (int i = 0; i < items2Size; i++) {
numsSize = insert(res, items2[i], numsSize);
}
*returnSize = numsSize;
*returnColumnSizes = (int *)malloc(sizeof(int) * numsSize);
for (int i = 0; i < numsSize; i++) {
(*returnColumnSizes)[i] = 2;
}
return res;
}