波波老师，能否提供一下leetcode451题的java版本的思路？

Question

波波老师，451个人感觉有点难，对于我这样的初学者，这道题给人一种看似简单，但是到了最后的字符串拼接，感觉就毫无头绪，网上的方法有很多，有些使用优先队列来做，有些是哈希表+数组，但是个人感觉看了他们的代码还是不是很懂，所以波波老师，可不可以给我一个思考这个题目的方向和建议呢？谢谢老师

Answer 1

liuyubobobo 2020-02-28 06:56:05

我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0451-Sort-Characters-By-Frequency/java-0451/src/Solution.java

我认为很好理解，不需要那么复杂的数据结构操作。

过程也很 straightforward。

首先，遍历字符串，获得每一个字符的频率；

然后，将一个一个（字符，频率）的数据对，包装在一个我们自己设计的 Pair 类中，一起放到一个 ArrayList 里。

对 ArrayList 中的所有的元素（Pair）进行排序。排序的方式是：谁的频率大，谁靠前。

这里，需要理解 Java 的 Comparable 接口和 compareTo 函数的设计。如果对于这部分语法不熟悉的话，需要找相关的教材或者资料看一下。Comparable 接口近乎是每一本 Java 教材一定会介绍的内容（在讲接口的时候），也是 Java 语法学习的一个重点。

排好序以后，就可以根据排序结果，一个一个取出（字符，频率）的数据对，把每个字符，重复频率那么多次，组成一个新的字符串。

拼接这个字符串的过程，应该使用 StringBuilder，而非 String，因为 String 是不可变的。对这一点不太理解的话，可以搜索一下 String 和 StringBuilder 的区别。

P.S.

对于你给的代码。是的，map.keySet() 就是将所有的 key 拿出来了，返回的是一个 Set，所以这个方法叫 keySet。这是 Map 设计的一个接口，for 循环已经在这个方法里面了。

map.keySet().toArray 方法则将结果转换成了一个数组。

里面为什么传入 new Integer[]{}，这就是一个语法，需要传入一个对象，告诉 Java 转换成的数组类型是什么。相应文档可以参考这里：https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#toArray-T:A-

不过整体我还是觉得我的方法比较容易懂。

继续加油！：）

• 提问者 v不离不弃v #1

  谢谢波波老师~~~！哎，我欠缺的知识太多了，好多知识点都不清楚，要是大学也是CS就好多了，很多知识点真的很无奈，现在是根本没办法学，只能在有限的时间里充分利用时间，把能补的知识点都补上呢，转专业真的太痛苦了，不过还是要万分感谢波波老师~

• liuyubobobo 回复 提问者 v不离不弃v #2

  可以理解。其实我相信这个算法的逻辑是很简单的，但是怎么具体用 Java 表达出来，需要对 Java 语言很熟练。没关系，其实做算法的过程，本身也是在锻炼学习深入语言。加油！：）

Answer 2

提问者 v不离不弃v 2020-02-27 04:49:02

波波老师，如果我将这题每个字母出现的次数作为哈希表的key，然后通过哈希表的value来将字母进行拼接，然后自己写一个build函数，将需要连接的字符和次数输入进去进行拼接：

String newStr= str.concat(build(ch, freq[i]));

                    map.put(freq[i], strNew);

那么结束后，在哈希表中的key如何排序呢？？哈希表不是无序的么？

下面是我在网上看到一个大神的解法，我对这个方法还不是很明白，通过map.keySet()就可以将所有的key就遍历出来了么？

2.这里我的意思是不是需要一个for循环才可以遍历？

3.然后不懂括号里面的new Integer[]{}为啥需要加这一个才可以将哈希表的key转化为数组。

Integer[] keys = map.keySet().toArray(new Integer[]{});

        Arrays.sort(keys);