题意整理。

• 输入数据表记录的索引以及对应数值。
• 将索引相同的记录进行合并，合并之后的值为所有对应值累加的结果。
• 最后按照索引值升序输出。

方法一（模拟）

1.解题思路

• 首先定义一个map，用于存放索引和对应的值，并将索引相同的记录进行合并。
• 然后用一个list记录map中所有的键，排序后，输出对应的结果。

2.代码实现

import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Collections;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //存放键值对
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            //用于接收索引
            int index=sc.nextInt();
            //用于接收数值
            int value=sc.nextInt();
            //合并相同索引，并存入map
            map.put(index,map.getOrDefault(index,0)+value);
        }
        
        //记录map的键，并排序
        ArrayList<Integer> list=new ArrayList<>();
        for(Integer key:map.keySet()){
            list.add(key);
        }
        Collections.sort(list);
        //按顺序打印key和value
        for(int i=0;i<list.size();i++){
            int key=list.get(i);
            System.out.println(key+" "+map.get(key));
        }
    }
}

3.复杂度分析

• 时间复杂度：需要遍历所有的键值对，以及对键进行排序，遍历的时间复杂度为$O(n)O(n)$，排序的时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$，所以时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$。
• 空间复杂度：需要额外大小为n的map以及大小为n（最坏情况下）的list，所以空间复杂度为$O(n)O(n)$。

方法二（TreeMap）

1.解题思路

与方法一的思路差不多，只是不用额外进行排序，因为TreeMap能保证插入的时候，所有的键是有序的。

动图展示：

2.代码实现

import java.util.Scanner;
import java.util.TreeMap;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //存放键值对
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int i=0;i<n;i++){
            //用于接收索引
            int index=sc.nextInt();
            //用于接收数值
            int value=sc.nextInt();
            map.put(index,map.getOrDefault(index,0)+value);
        }
        
        //按顺序打印key和value
        for(Integer key:map.keySet()){
            System.out.println(key+" "+map.get(key));
        }
    }
}

3.复杂度分析

• 时间复杂度：TreeMap中插入操作的时间复杂度为$O(lo{g}_{2}n)O(log\_2n)$，总共需要插入n次，所以时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$。
• 空间复杂度：需要额外大小为n的TreeMap，所以空间复杂度为$O(n)O(n)$。