笔试面试 | 扒一扒笔试面试中的编程题

©一颗斯特拉

1.字符串的排序和次数统计（3月25日）

题目：统计字符串中各字母数，例如abbbe，则输出a1b3e1。注意输出时要按ASCII码从小到大输出

01 方法

【桶计数】

思路

桶计数的思路是建立一个长度为 26 的数组表示 26 个桶，按顺序存放26个英文字母。实现本题目标，需要分两步走:
①先用的时间扫描一遍字符串（其中代表字符串的长度），统计每个字母出现的次数。
②然后将数组中不为0位置对应的字母和次数输出。

算法

建立一个长度为 26 的数组h[]，作为用来计数的「桶」。

复杂度分析

• 时间复杂度：

• 空间复杂度：这里使用了长度为 26 的数组作为辅助空间，故渐进空间复杂度为

02 源代码

#include<stdio.h>
#include<string.h>

int main(){
    char c[100];
    gets(c);
    int h[26];//存储26个英文字母
    int i,j;
    //给桶赋初值
    for(i=0;i<26;i++)
        h[i]=0;
    //统计每个字母出现的个数
    for(j=0;j<strlen(c);j++){
        h[c[j]- 'a']++;
    }
    //输出
    for(i=0;i<26;i++){
        if(h[i]!=0)
            printf("%c%d",i +'a',h[i]);
    }
    return 0;
}

【运行结果】

aabee
a2b1e2