Leetcode-451. Sort Characters By Frequency

98 阅读 0 评论 65 点赞

我是靠谱客的博主清爽酸奶，最近开发中收集的这篇文章主要介绍Leetcode-451. Sort Characters By Frequency，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言：为了后续的实习面试，开始疯狂刷题，非常欢迎志同道合的朋友一起交流。因为时间比较紧张，目前的规划是先过一遍，写出能想到的最优算法，第二遍再考虑最优或者较优的方法。如有错误欢迎指正。博主首发CSDN，mcf171专栏。

博客链接：mcf171的博客

——————————————————————————————

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.
Note that "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.

这个想法就是用一个新的类，保存字符是什么，以及当前字符多少个了，最后对于这个List进行排序即可。 Your runtime beats 71.22% of java submissions.

public class Solution {
    public String frequencySort(String s) {
        Map<Character, Product> map = new HashMap<Character, Product>();
        List<Product> list = new ArrayList<Product>();
        for(char item : s.toCharArray()){
            if(map.containsKey(item)){
                Product product = map.get(item);
                product.sb.append(item);
                product.count ++;
            }else{
                Product product = new Product();
                product.sb.append(item);
                product.count = 1;
                list.add(product);
                map.put(item, product);
            }
        }
        Collections.sort(list, new Comparator<Product>(){
            public int compare(Product p1, Product p2){
                return p2.count - p1.count;
            }
        });

        StringBuffer sb = new StringBuffer("");
        for(Product item : list){
            sb.append(item.sb);
        }
        return sb.toString();
    }

    class Product{
        int count;
        StringBuffer sb = new StringBuffer("");
    }
}