Leetcode 451 根据字符出现频率排序

@(C++)[leetcode]

1.思路

1. 初始化一个长度为48的数组，记录各个字母的个数
2. 扫描一遍输入字符串，更新数组的值
3. 对数组进行排序

2尝试过程中第一版本代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string frequencySort(string s) {
    vector<int> alphabet_count;
    // 24 for small 24 for big
    for(int i=0;i<24;i++) {
        alphabet_count.push_back(0);
        alphabet_count.push_back(0);
    }
    for(char c : s){
        if( c >= 'a' && c <= 'z'){
            alphabet_count[c-'a']++;
        }else if(c >= 'A' && c <= 'Z'){
            alphabet_count[c-'A'+24]++;
        }
    }
    for(int i=0;i<24;i++){
        cout<<char(i+'a')<<",";
    }
    for(int i=0;i<24;i++){
        cout<<char(i+'A')<<",";
    }
    cout<<endl;
    for(int i : alphabet_count){
        cout<<i<<",";
    }
    cout<<endl;
    return s;
}

int main(){
    string s = "abcdefgABCDEFG";
    frequencySort(s);
    return 0;
}

输出结果，可以正确统计各个字母的数量

a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X
1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

2.1遇到的问题

但是对数组排序之后，信息丢失，不知道哪个数字对应哪一个字母。

2.2 想想解决办法

可以定义一个结构体，结构体每部包含两个属性:

1. 字母
2. 字母出现的个数

3 新的方案

3.1 定义结构体，写构造函数

struct alphabet
{
    char c;
    int count;
    alphabet(char c, int n):c(c),count(n){}
};

3.2 改写函数

实现了对结构体的排序，这边直接调用了 #include <algorithm>中的sort()

string frequencySort(string s) {
    vector<alphabet> alphabets;
    for(int i=0;i<24;i++) {
        alphabets.push_back(alphabet('a'+i,0));
    }
    for(int i=0;i<24;i++) {
        alphabets.push_back(alphabet('A'+i,0));
    }
    for(char c:s){
        if( c >= 'a' && c <= 'z'){
            alphabets[c-'a'].count++;
        }else if(c >= 'A' && c <= 'Z'){
            alphabets[c-'A'+24].count++;
        }
    }
    sort(alphabets.begin(),alphabets.end(),[](const alphabet &a, const alphabet &b) {
            return a.count > b.count;
    });
    string result;
    for(alphabet a:alphabets){
        for(int i = 0;i<a.count;i++){
            result.push_back(a.c);
        }
    }
    return result;
}

3.3 提交！

发现没考虑数字的情况！！！！！！！

部分没过

加上数字的情况再试一下，改的过程中发现了问题！是26个字母不是24个字母啊！！！！！

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;


// @lc code=start
class Solution {
public:
    struct alphabet
    {
        char c;
        int count;
        alphabet(char c, int n):c(c),count(n){}
    };
    string frequencySort(string s) {
        vector<alphabet> alphabets;
        for(int i=0;i<26;i++) {
            alphabets.push_back(alphabet('a'+i,0));
        }
        for(int i=0;i<26;i++) {
            alphabets.push_back(alphabet('A'+i,0));
        }
        for(int i=0;i<10;i++) {
            alphabets.push_back(alphabet('0'+i,0));
        }
        for(char c:s){
            if( c >= 'a' && c <= 'z'){
                alphabets[c-'a'].count++;
            }else if(c >= 'A' && c <= 'Z'){
                alphabets[c-'A'+26].count++;
            }else if(c >= '0' && c <= '9'){
                alphabets[c-'0'+52].count++;
            }
        }
        sort(alphabets.begin(),alphabets.end(),[](const alphabet &a, const alphabet &b) {
                return a.count > b.count;
        });
        string result;
        for(alphabet a:alphabets){
            for(int i = 0;i<a.count;i++){
                result.push_back(a.c);
            }
        }
        return result;
    }
};

过了！

AC

4 也可以用 unordered_map代替结构体