统计数字（蓝桥杯）

题目描述

某次科研调查时得到了 n 个自然数，每个数均不超过 1.5≤109。已知不相同的数不超过 10^4个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入描述

第 1 行是整数 n，表示自然数的个数。

第 2 ~ n+1行每行一个自然数。

其中， 10^5，每个数均不超过 1≤n≤2×10^5，每个数均不超过1.5≤10^9。

输出描述

输出 m 行（ m 为 n 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

输入输出样例

示例 1

输入

8
2
4
2
4
5
100
2
100

输出

2 3
4 2
5 1
100 2

 

这是第一次写的时候，测试用例是对的，但提交时不对，原因时用了两个for循环，当测试用例比较大时，就会超时，这样时间算法复杂度为O(n^2)。

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int []arr=new int[n];
        int []match=new int[n];//用来记录是否已经找过
        for(int i=0;i 
第二次修改，这样时间算法复杂度为O(n)
 
import java.util.Scanner;
import java.util.Arrays;
import java.util.linkedList;

public class Main{
    public static void main(String[] args) {
     Scanner in=new Scanner(System.in);
     int n=in.nextInt();
    int []arr=new int[n];
    int []match=new int[n];
    for(int i=0;i