P1097 统计数字

我又来水题了(连 普及- 的题目都不放过)

题目描述

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

题目标签

算法标签:模拟,排序,概率论

输入格式

n + 1 行。

第一行是整数n,表示自然数的个数;

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

输出格式
共m行(m为n个自然数中不相同数的个数),按照自然数从小到大的顺序输出。

每行输出2个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。

题解

本帖搬运自 小卓的博客 - LuoGu我抄我自己

很简单的一道题:套个快排模板,再做下简单的处理就行了。

看到很多大佬先排序再处理重复的数据,而我的做法是先处理掉重复数据再排序。

#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;
}

这种做法可以使重复数据不进入排序程序中,而是直接进行统计。

好久没更新博客了,水道题就跑

Last modification:August 22nd, 2020 at 10:00 pm
如果觉得我的文章对你有用,请随意赞赏