P1097 统计数字——题解

思路

把所有数放入数组后排序。排序完成后，相同数字一定连续出现。

从左到右扫描：

• 记录当前数字 a[i]；
• 继续向右找到第一个与它不同的位置；
• 两个位置之差就是该数字出现的次数；
• 输出后继续处理下一段。

复杂度

排序时间复杂度 $O(n\log n)$，扫描为 $O(n)$，空间复杂度 $O(n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long a[200005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    int i = 1;
    while (i <= n) {
        int j = i;
        while (j <= n && a[j] == a[i]) j++;
        cout << a[i] << ' ' << j - i << '\n';
        i = j;
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; long long a[200005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); int i=1; while(i<=n){ int j=i; while(j<=n&&a[j]==a[i]) j++; cout<<a[i]<<' '<<j-i<<'\n'; i=j; } return 0; }