Comparator
Comparator is an interface, we can override the compare method to customize our sorting
对于数组、链表、堆等结构，标准库中排序方法，往往是对于基本类型的升序排序，有的时候，不一定能满足我们的要求。例如我们有一些特殊的顺序要求，或待排序的对象类型不是基本类型。此时，就需用到自定义排序。自定义排序可以用在很多地方，比如数组排序，堆的排序规则等。Java实现自定义排序，主要有两种方法：
1.实现Comparable接口：
以Interval区间为例，在定义该类时，让其实现Comparable，并重写其中的compareTo方法，使得Interval类可以进行大小比较，这样也可实现自定义的排序：
class Interval implements Comparable<Interval> {
int left, right;
Interval(int left, int right) {
this.left = left;
this.right = right;
}
@Override
public int compareTo(Interval o) {
return this.left - o.left;
}
}这样，在其他地方就可以直接对Interval对象的大小进行比较。完整的测试方法如下：
import java.util.ArrayList;
import java.util.List;
import static java.util.Collections.sort;
// Interval类如上
public class Main {
public static void main(String[] args) {
List<Interval> A = new ArrayList<>();
A.add(new Interval(1, 7));
A.add(new Interval(5, 6));
A.add(new Interval(3, 4));
System.out.println("Before sort:");
for (Interval i : A)
System.out.println("(" + i.left + ", " + i.right + ")");
sort(A);
System.out.println("After sort:");
for (Interval i : A)
System.out.println("(" + i.left + ", " + i.right + ")");
}
}输出可以自行观察，不再赘述。
2.定义比较类：
该方法定义一个新的比较类，使其继承自Comparator，并完善其中的compare()方法。在调用时，使用该比较类进行比较。仍以Interval为例：
class Interval { // 注意，这里没有继承自Comparable
int left, right;
Interval(int left, int right) {
this.left = left;
this.right = right;
}
}
class MyCmp implements Comparator<Interval> {
@Override
public int compare(Interval o1, Interval o2) {
return o1.left - o2.left;
}
}要对List<Interval> A进行排序时，调用如下方法，填入一个比较类的对象即可：
A.sort(new MyCmp());/**
* Definition for a Connection.
* public class Connection {
* public String city1, city2;
* public int cost;
* public Connection(String city1, String city2, int cost) {
* this.city1 = city1;
* this.city2 = city2;
* this.cost = cost;
* }
* }
*/
Collections.sort(connections, new Comparator<Connection>() {
public int compare(Connection a, Connection b) {
if (a.cost != b.cost) {
return a.cost - b.cost;
}
if (!a.city1.equals(b.city1)) {
return a.city1.compareTo(b.city1);
}
return a.city2.compareTo(b.city2);
}
});原生数组
public int[][] multiSort(int[][] array) {
// Write your code here
Arrays.sort(array, new Comparator<int[]>() {
public int compare(int[] l, int[] r) {
if (l[1] != r[1]) {
return r[1] - l[1];
}
return l[0] - r[0];
}
});
return array;
}Coding Problem
Description
Give a new alphabet, such as {c,b,a,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}. Sort the string array according to the new alphabet
Example - Verifying an Alien Dictionary
Given Alphabet ={c,b,a,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}, String array ={cab,cba,abc}, return{cba,cab,abc}.
Explanation:
According to the new dictionary order, output the sorted result {cba, cab, abc}.Given Alphabet ={z,b,a,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,c}, String array ={bca,czb,za,zba,ade}, return{zba,za,bca,ade,czb}.
Explanation:
According to the new dictionary order, output the sorted result {zba,za,bca,ade,czb}.public class Solution {
/**
* @param alphabet: the new alphabet
* @param words: the original string array
* @return: the string array after sorting
*/
public String[] wordSort(char[] alphabet, String[] words) {
// Write your code here
Arrays.sort(words, new WordComparator(alphabet));
return words;
}
class WordComparator implements Comparator<String> {
Map<Character, Integer> map = new HashMap<>();
public WordComparator(char[] alphabet) {
for (int i = 0; i < alphabet.length; i++) {
map.put(alphabet[i], i);
}
}
public int compare(String a, String b) {
int minLen = Math.min(a.length(), b.length());
for (int i = 0; i < minLen; i++) {
int aValue = map.get(a.charAt(i));
int bValue = map.get(b.charAt(i));
if (aValue == bValue) {
continue;
} else {
return aValue - bValue;
}
}
return a.length() - b.length();
}
}
}Sort by Frequency:
import java.util.*;
public class GFG {
// Driver Code
public static void main(String[] args)
{
// Declare and Initialize an array
int[] array = { 4, 4, 2, 2, 2, 2, 3, 3, 1, 1, 6, 7, 5 };
Map<Integer, Integer> map = new HashMap<>();
List<Integer> outputArray = new ArrayList<>();
// Assign elements and their count in the list and map
for (int current : array) {
int count = map.getOrDefault(current, 0);
map.put(current, count + 1);
outputArray.add(current);
}
// Compare the map by value
SortComparator comp = new SortComparator(map);
// Sort the map using Collections CLass
Collections.sort(outputArray, comp);
// Final Output
for (Integer i : outputArray) {
System.out.print(i + " ");
}
}
}
// Implement Comparator Interface to sort the values
class SortComparator implements Comparator<Integer> {
private final Map<Integer, Integer> freqMap;
// Assign the specified map
SortComparator(Map<Integer, Integer> tFreqMap)
{
this.freqMap = tFreqMap;
}
// Compare the values
@Override
public int compare(Integer k1, Integer k2)
{
// Compare value by frequency
int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));
// Compare value if frequency is equal
int valueCompare = k1.compareTo(k2);
// If frequency is equal, then just compare by value, otherwise -
// compare by the frequency.
if (freqCompare == 0)
return valueCompare;
else
return freqCompare;
}
}Last updated