某次科研调查时得到了 � n 个自然数，每个数均不超过 1.5 ≤ 1 0 9 1.5≤10 9 。已知不相同的数不超过 1 0 4 10 4 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 输入描述 第 1 行是整数 � n，表示自然数的个数。 第 2 ~ � n+1行每行一个自然数。 其中， 1 ≤ � ≤ 2 × 1 0 5 ，每个数均不超过 1.5 ≤ 1 0 9 1≤n≤2×10 5 ，每个数均不超过1.5≤10 9 。 输出描述 输出 � m 行（ � m 为 � n 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。用Java代码编写

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

相关问题

用c加加stl算法实现某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5∗10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

这个问题可以使用C++ STL中的map容器来解决。具体做法如下：

1. 定义一个map<int, int>类型的变量count_map来存储每个自然数的出现次数，其中map的key表示自然数，value表示出现次数。

2. 读入n个自然数，对于每个自然数num，通过count_map[num]++来增加它的出现次数。

3. 遍历count_map，按照自然数从小到大的顺序输出统计结果。

下面是代码实现：

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    map<int, int> count_map;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        count_map[num]++;
    }
    for (map<int, int>::iterator it = count_map.begin(); it != count_map.end(); ++it) {
        cout << it->first << " " << it->second << endl;
    }
    return 0;
}

这个算法的时间复杂度为O(nlogn)，其中logn来自于map的插入和查找操作的时间复杂度。可以通过unordered_map来优化为O(n)的时间复杂度，但是由于数据范围较小，使用map已经足够快速和可靠。

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

### 回答1：
这是一道科研调查题，得到了n个自然数，每个数均不超过1500000000（1.5*10^9）。已知不同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

### 回答2：
这道题目可以用哈希表来解决，因为题目中要求的是对每一个出现的自然数进行计数，按照自然数从小到大的顺序输出结果。哈希表适合这种需要查找、计数和排序的场景，而且哈希表的时间复杂度比较低。

具体地，我们可以用一个数组来实现哈希表。假设我们的 n 个自然数中最大的数是 m，那么我们可以定义一个长度为 m+1 的数组 count，count[i] 表示 i 这个自然数出现的次数。然后，我们遍历这 n 个自然数，对于每一个数 x，我们就在 count 数组对应的位置 count[x] 中增加 1。

这样，我们就完成了对每一个自然数出现次数的统计。最后，我们按照自然数从小到大的顺序遍历一遍 count 数组，输出出现次数不为 0 的自然数即可。

需要注意的是，因为数组的长度可能很大，所以我们需要把数组定义成 long long 类型，而不是 int 类型。

代码如下：

#include <iostream>

using namespace std;

const int MAXN = 1500000005;

long long cnt[MAXN];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int i = 1; i <= MAXN; i++) {
        if (cnt[i]) {
            cout << i << " " << cnt[i] << endl;
        }
    }

    return 0;
}

复杂度分析：

时间复杂度：O(n+m)，其中 n 是自然数的个数，m 是最大自然数大小。遍历一遍 n 个自然数的时间复杂度是 O(n)，遍历一遍长度为 m+1 的数组的时间复杂度是 O(m)。

空间复杂度：O(m)，需要开辟一个长度为 m+1 的数组存储自然数出现的次数。

### 回答3：
这是一道典型的计数问题，可以使用哈希表（Hash Table）进行解决。首先，我们可以创建一个长度为 1500000000 的数组count，用于记录每个数出现的次数。遍历输入的 n 个数，将每个数作为数组的下标，其对应的元素加一。统计完成后，按照自然数从小到大的顺序输出非零元素即可。

不过，由于n的大小不确定，我们需要采用一些优化措施来减少时间和空间复杂度。一个显而易见的优化就是使用哈希表。哈希表是一种以键-值（key-value）存储数据的数据结构，它能够支持常数时间复杂度的插入和查找操作。

我们可以使用 STL 中的unordered_map来实现哈希表，并遍历输入的 n 个数，将每个数作为键，其对应的值为出现的次数。统计完成后，按照自然数从小到大的顺序输出非零元素即可。

另一个优化措施是使用桶排序。桶排序是一种线性排序算法，它将要排序的数据分到有限数量的桶子里，每个桶子再分别排序。对于本问题，我们可以使用长度为 1500000000 的桶来记录每个数出现的次数，遍历输入的 n 个数，将每个数放到其对应的桶里。统计完成后，按照自然数从小到大的顺序输出非零元素即可。

最终，我们需要评估这三种算法的时间复杂度和空间复杂度，以确定最优解。哈希表的时间复杂度是 O(N)，空间复杂度是 O(N)；桶排序的时间复杂度是 O(N)，空间复杂度是 O(M)，其中 M 为桶的数量；而使用数组的方法时间复杂度虽然也是 O(N)，但空间复杂度是 O(M)，其中 M 为数组的长度。因此，在数据规模较小的情况下，使用数组的方法较为合适；在数据规模较大的情况下，使用哈希表或桶排序较为合适。