题解 【P1097 统计数字】
小卓
2020-08-22 21:46:53
很简单的一道题：套个快排模板，再做下简单的处理就行了。
看到很多大佬先排序再处理重复的数据，而我的做法是先处理掉重复数据再排序。
```cpp
#include <iostream>
#include <map>
using namespace std;
map<long long,int> stat;
long long a[200005];
// 快排模板（不多说）
void qsort(long long a[], int left, int right) {
if(left < right){
int i = left;
int j = right;
int x = a[left];
while(i<j)
{
while(i < j && a[j] > x){
j--;
}
if(i < j){
a[i++] = a[j];
}
while(i < j && a[i] < x){
i++;
}
if(i < j){
a[j--] = a[i];
}
}
a[i] = x;
qsort(a,left,i - 1);
qsort(a,i + 1,right);
}
}
int main(){
int n, rn = 0,df = 0;
// rn 用于存放最终被排序的数量
// df 用于存放当前偏差值（循环偏差）
cin >> n;
for(int i = 1; i <= n; i++){
long long x;
cin >> x;
// 检查输入的值是否已存在
if(stat[x] == 0){
stat[x] = 1;
a[i - df] = x; // 存入数组
// 这里的偏差是我临时想出来的解决方法：
// 本循环会读入部分重复的值
// 这些值并不会被存入数组，会导致 a 数组有空间为0
// 增加 diff 后可以规避这种问题
// 出现一次重复就在下一次新存放值时对 i - 1
rn ++; // 统计结果数
}else{
stat[x] ++; // 出现次数 ++
df ++; // 偏差值 ++
}
}
qsort(a,1,rn); // 调用快排函数
// 输出最终的结果
for(int i = 1; i <= rn; i++){
long long num = a[i];
cout << num << " " << stat[num] << endl;
}
return 0;
}
```
这种做法可以使重复数据不进入排序程序中，而是直接进行统计