451. Sort Characters By Frequency（python+cpp）-白红宇

451. Sort Characters By Frequency（python+cpp）

阅读量：3704 次

发布时间：2019-05-21

本文共 2060 字，大约阅读时间需要 6 分钟。

题目：

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input: "tree"Output: "eert"Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: "cccaaa"Output: "cccaaa"Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Notethat "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: "Aabb"Output: "bbAa"Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

解释：

先统计，再根据出现的频率排序。

在python中需要用item()函数把字典键值对转成元组，在c++中需要转成pair 数组，而且要自己实现一下排序函数。

python代码：

from collections import Counterclass Solution(object):    def frequencySort(self, s):        """        :type s: str        :rtype: str        """        _dict=Counter(s)        sort_dict=sorted(_dict.items(),key=lambda item:item[1],reverse=True)        result=''        for item in sort_dict:            result+=item[0]*item[1]        return result

c++代码：

#include using namespace std;class Solution {
   public:    string frequencySort(string s) {
           map
    
      _map;        for(auto letter:s)            _map[letter]+=1;        //把map转换成数组        vector
     
      
       > map_list(_map.begin(),_map.end());        sort(map_list.begin(),map_list.end(),cmp);        string result="";        for (auto item :map_list)        {
               string tmp(item.second, item.first);            result+=tmp;        }        return result;    }    static bool cmp(const pair
       
        & item1,const pair
        
         & item2) { return item1.second>item2.second; }};

总结：

python中，d.items()实际上是将d转换为可迭代对象，迭代对象的元素为（‘lilee’,25）、（‘wangyan’,21）、（‘liqun’,32）、（‘lidaming’,19），items()方法将字典的元素转化为了元组，而这里key参数对应的lambda表达式的意思则是选取元组中的第二个元素作为比较参数（如果写作key=lambda item:item[0]的话则是选取第一个元素作为比较对象，也就是key值作为比较对象。lambda x:y中x表示输入参数，y表示lambda函数的返回值），所以采用这种方法可以对字典的value进行排序。注意排序后的返回值是一个list，而原字典中的键值对对被转换为了list中的元组。

转载地址：http://kwmcn.baihongyu.com/

你可能感兴趣的文章