这个问题的提出,是因为刷题的时候总会遇到类似于Arrays.sort(nums)这种情形。这种情况下,排序是默认升序的,若想变成降序或者其它自定义的排序方式,这又该怎么处理呢?下面介绍一下做题过程中这种要怎么处理。


Comparator接口

Comparator接口是util包下的比较器接口,里面有compare和equals方法。

package java.util;

public interface Comparator<T> {
	// 写算法题时尝尝会重写这个方法!
    int compare(T o1, T o2);

    boolean equals(Object obj);
}

它是一种外部比较器,若想控制某个类的集合元素的次序,可以实现该类的比较器来排序。

下面展示一个例子

一个 句子 指的是一个序列的单词用单个空格连接起来,且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。

我们可以给一个句子添加 从 1 开始的单词位置索引 ,并且将句子中所有单词 打乱顺序 。

比方说,句子 "This is a sentence" 可以被打乱顺序得到 "sentence4 a3 is2 This1" 或者 "is2 sentence4 This1 a3" 。
给你一个 打乱顺序 的句子 s ,它包含的单词不超过 9 个,请你重新构造并得到原本顺序的句子。

示例 1:

输入:s = "is2 sentence4 This1 a3"
输出:"This is a sentence"
解释:将 s 中的单词按照初始位置排序,得到 "This1 is2 a3 sentence4" ,然后删除数字。
示例 2:

输入:s = "Myself2 Me1 I4 and3"
输出:"Me Myself and I"
解释:将 s 中的单词按照初始位置排序,得到 "Me1 Myself2 and3 I4" ,然后删除数字。

提示:

2 <= s.length <= 200
s 只包含小写和大写英文字母、空格以及从 1 到 9 的数字。
s 中单词数目为 1 到 9 个。
s 中的单词由单个空格分隔。
s 不包含任何前导或者后缀空格。

这个题目很容易吧,只要按每个单词的最后一个数字的大小来排序就行了,重写Comparator接口即可。

class Solution {
    public String sortSentence(String s) {
        String[] strs = s.split(" ");
        Arrays.sort(strs, 
            //  重点!
            new Comparator<String>(){
                public int compare(String s1, String s2){
                    // 比较单词的最后一个数字的大小
                    int n1 = s1.charAt(s1.length() - 1);
                    int n2 = s2.charAt(s2.length() - 1);
                    return Integer.compare(n1, n2);
                }
        });
        // 拼接排序后的结果
        StringBuilder sb = new StringBuilder();
        for(String str : strs){
            sb.append(str, 0, str.length() - 1).append(" ");
        }
        return sb.toString().trim();
    }
}

也可以把它写成lambda表达式的形式,更简洁。

Arrays.sort(strs, (s1, s2)->{
    // 比较单词的最后一个数字的大小
    int n1 = s1.charAt(s1.length() - 1);
    int n2 = s2.charAt(s2.length() - 1);
    return Integer.compare(n1, n2);
});

Comparable接口

Comparable是lang包的一个内部排序接口,里面有一个compareTo方法。一个类只要实现了它,就意味着这个类支持排序,这个接口就是一个内部比较器。

某个类实现了Comparable接口,就要重写里面的compareTo方法。

package java.lang;
import java.util.*;

public interface Comparable<T> {
    public int compareTo(T o);
}

引入的一道题

其实这个知识点以前碰到过很多次了,但是都没有怎么记录,而且用的话好像也不大会用,没想到啊,前段时间的面试就碰到了。

前些天做了做4399的面试题,里面有一道和leetcode692差不多的题目,当时有那种思路,但是却不知道如何下手,才知道是自己不熟悉这种重写比较器实现自定义排序。

题目如下:

给一非空的单词列表,返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。

示例 1:

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 "i" 在 "love" 之前。

示例 2:

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。

注意:

假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。

扩展练习:

尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

方法一

我看到题目,找前k个,马上想到了使用优先队列,但是优先队列只能存“一个东西”啊,它不能把单词和单词对应的频次一起存进去,这就不好比较了。所以做笔试题的时候,想到这里我就不知道接下来该怎么做了。

这里和上面Comparator给的例子一样的,只要重写优先队列的比较器就行了,按照它的词频进行排序就行了!词频可以使用哈希表存储。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>(words.length);
        for(String word : words){
            // 统计词频
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> queue = new PriorityQueue<>((o1, o2)->{
            // 按照词频顺序建立堆
            Integer o1Count = map.get(o1);
            Integer o2Count = map.get(o2);
            if(o1Count.equals(o2Count)){
                return o2.compareTo(o1);
            }else{
                return o1Count - o2Count;
            }
        });
        for(String word : map.keySet()){
            queue.offer(word);
            // 把超过k个的全部删除,剩下的k个就是前k个高频词
            if(queue.size() > k){
                queue.poll();
            }
        }
        // 最后拼接,得到结果
        LinkedList<String> stack = new LinkedList<>();
        while(!queue.isEmpty()){
            stack.push(queue.poll());
        }
        return stack;
    }
}

方法二

上面的是重写堆的比较器,下面也可以使用哈希表+排序来实现,这次就实现排序方法的比较器。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>(words.length);
        for(String word : words){
            // 统计词频
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<String> res = new ArrayList<>();
        // 把map的key加进去List中
        for(Map.Entry<String, Integer> entry : map.entrySet()){
            res.add(entry.getKey());
        }
        Collections.sort(res, new Comparator<String>(){
            public int compare(String word1, String word2){
                // 比较在map中,word1的词频和word2的词频关系
                return map.get(word1) == map.get(word2) ? 
                    word1.compareTo(word2) : map.get(word2) - map(word1);
            }
        });
        // 截断前k个,因为比较器写的是降序
        return  res.subList(0, k);
    }
}

一个小问题

我们知道,Comparator中的compare方法的返回值,其实是按照正、负、零来决定两个元素之间的大小的,但是我怎么知道哪个比哪个大,它就是升序,哪个比哪个小,它就是降序呢?

这个好像要看源码,我暂时也不大清楚……比如Arrays.sort()中,它里面有关元素比较的时候,肯定也是用到了这个compare方法,而这个方法的内容就是我们重写的内容,由我们写的东西来决定源码排序的大小区分。

Returns:

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

但是我发现一个可以浑水摸鱼的好技巧【x】。

两个元素,比如是(n1, n2),如果结果是n1-n2的话,就是“默认的升序”,排序来说,就是前面的小,后面的大,堆的话就是小顶堆;若是n2-n1,则是"降序",前面的大,后面的小,堆的话就是大堆顶。

这个规律应该是正确的,可以暂时这样用着先……