算法思路

题目要求我们对输入的多个键值对进行合并，合并规则是：如果两个或多个键值对具有相同的索引 index，则将它们的 value 值相加，最后按照 index 升序输出合并后的结果。

解决思路：

  1. 数据存储：使用一个哈希表（JavaScript 中为对象或 Map）来存储每个 index 对应的累积值。
  2. 处理输入：逐行读取输入的 index 和 value，将相同 index 的 value 累加。
  3. 排序输出：将存储的哈希表按 index 升序排序，并输出结果。

步骤：

  1. 读取输入的键值对个数 n。
  2. 用哈希表存储每个 index 对应的总和。
  3. 遍历哈希表的键，按照 index 升序输出合并后的键值对。

Code

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 读取键值对的个数
    let n = parseInt(await readline());
    
    // 创建一个哈希表来存储合并后的结果
    let map = new Map();

    // 读取每一行的 index 和 value
    for (let i = 0; i < n; i++) {
        let [index, value] = (await readline()).split(' ').map(Number);
        
        // 如果 index 已经存在，累加 value；如果不存在，直接设置
        if (map.has(index)) {
            map.set(index, map.get(index) + value);
        } else {
            map.set(index, value);
        }
    }

    // 将 map 的键（index）按升序排序
    let sortedKeys = Array.from(map.keys()).sort((a, b) => a - b);

    // 输出合并后的键值对
    for (let key of sortedKeys) {
        console.log(`${key} ${map.get(key)}`);
    }
}()

.map(Number)：

  • .map(Number) 是数组的一个方法，它会对数组中的每个元素应用 Number 函数。Number 函数会将字符串转换为数字。
  • 所以，["0", "1"] 会变成 [0, 1]。这里，0 和 1 是数字类型，而不是字符串。

复杂度分析

  • 时间复杂度：O(n log n)，其中 n 是输入的键值对个数。我们首先遍历了输入的每一行（O(n)），然后对 map 的键进行排序（O(n log n)）。
  • 空间复杂度：O(n)，我们使用了一个哈希表（Map）来存储每个 index 对应的累积值，最多存储 n 个键值对，因此空间复杂度为 O(n)。