自定义排序与Arrays.sort()
本篇题目来源:2022/11/13 Leetcode每日一题:https://leetcode.cn/problems/custom-sort-string
给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的,并且以前按照一些自定义的顺序排序。
对 s 的字符进行置换,使其与排序的 order 相匹配。更具体地说,如果在 order 中的字符 x 出现字符 y 之前,那么在排列后的字符串中, x 也应该出现在 y 之前。
返回 满足这个性质的 s 的任意排列 。
示例1:
输入: order = "cba", s = "abcd"
输出: "cbad"
解释:
“a”、“b”、“c”是按顺序出现的,所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的,所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
示例2:
输入: order = "cbafg", s = "abcd"
输出: "cbad"
这是一道字符串自定义排序题,即按照一个约定的顺序,给字符串进行排序。
对于数组,Java提供了一个排序方法:Arrays.sort()。该函数有多个重载,对基本类型和引用类型均有排序。不过对于基本类型来说,只可按照默认顺序进行排序,无法自定义Comparator;而对于引用类型,则可以自定义Comparator以实现自定义排序的效果。
- 基本类型也可以通过对应的包装类以实现自定义排序的功能
解题
1.对于这道题来说,首先需要将给定的顺序:order数组转为一个可比较顺序的int[]:
//表顺序的数组,这样,调用orders[c] = i即可表示:c排在order中的第i位
int[] orders = new int[26];
for(int i = 0; i < order.length(); ++i) {
orders[order.charAt(i) - 'a'] = i;
}
2.有了顺序后,就可以使用Arrays.sort()进行自定义排序:
//使用char的包装类Character以支持自定义排序
Character[] ans = new Character[s.length()];
for(int i = 0; i < s.length(); ++i) {
ans[i] = s.charAt(i);
}
//使用lambda表达式来简化Comparator的内容
Arrays.sort(ans, (c1, c2) -> orders[c1 - 'a'] - orders[c2 - 'a']);
扩展
实际上,Java不仅对数组类型提供了Arrays.sort()方法,对List类型同样提供了sort()方法,并且功能基本一致
同样,也可以对List的内容进行自定义排序,比如,有一个People实体类,结构如下:
public class People {
private String name;
private int age;
public People(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "People{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
现在,想根据People实体类中的age参数对People List进行排序,就可以通过List中的sort()方法来写自定义的Comparator:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class PeopleSortDemo {
public static void main(String[] args) {
People p1 = new People("Bob", 25);
People p2 = new People("Lily", 30);
People p3 = new People("Li Ming", 18);
List<People> peopleList = new ArrayList<>();
peopleList.add(p1);
peopleList.add(p2);
peopleList.add(p3);
peopleList.sort((pa, pb) -> pa.getAge() - pb.getAge());
System.out.println(peopleList);
}
}
结果如下: