Leetcode 451. Sort Characters By Frequency

Posted on | In |

array 排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
array<int,128> v;
bool cmp(char a,char b){
        if(v[a]!=v[b])
        return v[a]>v[b];
        else return a>b;
}
class Solution {
public:
    string frequencySort(string s) {
        v={0};//!!
        for(int i=0;i<s.length();i++){
            v[s[i]]++;
        }
       sort(s.begin(),s.end(),cmp);
       return s;
    }
};

map 排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
map<char,int> v;
bool cmp(char a,char b){
        if(v[a]!=v[b])
        return v[a]>v[b];
        else return a>b;
}
class Solution {
public:
    string frequencySort(string s) {
        v.clear();
        for(int i=0;i<s.length();i++){
          //  if(!v.count(s[i]))
           // v[s[i]]=1;
            //  else v[s[i]]++; 可省略 初始化 所有键的值为0
            v[s[i]]++;
        }
       sort(s.begin(),s.end(),cmp);
       return s;
    }
};

couting 计数思想

用vector<pair<int，char>> 存次数和其对应的字符
按次数降序 构成一个新的string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string frequencySort(string s) {
        vector<int> f(128,0);
         for(int i=0;i<s.length();i++){
             f[s[i]]++;
        }
        vector<pair<int,char>> v;
       for(int i=0;i<128;i++){
           if(f[i]>0)
           v.push_back(pair<int,int>(f[i],i));
       }
       sort(v.rbegin(),v.rend());
       string ans;
            for(auto t:v){
                ans.append(t.first,t.second);
            }
           
       
       return ans;
    
    }
};

参考链接

关于empalce_back 和 push_back
https://blog.csdn.net/xiaolewennofollow/article/details/52559364