文章目录
- 前言
- 思考
- 思路
- 代码
- 对Value排序
- 扩展
- 测试
- int类型数据
- String类型数据
- 对Key排序
- 测试
- String类型数据
前言
本篇文章总结来自九月份的每日一题
347-前K个高频的元素
思考
对于系列的题目就是计算利用到Hash表的属性的Key与Value的双属性，能够满足我们后面计算对于每一个元素出现的频率的同时还能够保存对于Key值的一一对应，能够让我们得以进行系列的计算与操作，其实对于Hash表的使用最明显的莫过于LeetCode的第一题：两数之和和其变形三数之和，都有利用到Hash来判断某一个值是否存在或者对其的Value进行系列的增加或删除操作，不需要我们进行遍历判断，且是线性。
思路
还是和之前一样，我们先对数组中的值进行频率的计算，对于不在数组其中的值对其的Value进行设置为1，对于已经存在数组其中的值对其的Value进行加一处理：
for(int value: nums){
if(map.containsKey(value)){
map.put(value,map.get(value)+1);
}
else{
map.put(value,1);
}
在将所有的数据都存在Map中以后，剩下的就是如何将其中value值比较高的前K个取出来，也就转换成为了如何对Map中的Value进行排序处理？排序完成之后，就可以顺序取出来前K个也就是我们想要的前K高的元素。
代码
public int [] topKFrequent(int[] nums, int k) {
int []num = new int[k];
Map<Integer,Integer> map = new HashMap<>();
for(int value: nums){
if(map.containsKey(value)){
map.put(value,map.get(value)+1);
}
else{
map.put(value,1);
}
}
List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o2.getValue()-o1.getValue();
}
});
Map<Integer,Integer> resultMap = new HashMap<>();
for(Map.Entry<Integer,Integer> entry: list){
resultMap.put(entry.getKey(),entry.getValue());
}
for(int i = 0 ;i<k;i++){
num[i]= list.get(i).getKey();
}
return num;
}
对Value排序
一想到这种并非是常规的数值的排序就想到了Collections.sort但是对于其来说接收的是List类型，于是我们就定义Map类型的List。
List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
解释：
对于Map.Entry来说就是Map中的一个接口，其是一个映射项，包含getKey和getValue方法
对于map.entrySet来说返回的而是Map中各个键值对映射关系的集合。
举个例子：
Iterator<Map.Entry<Integer, Integer>> it=map.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Integer,Integer> entry=it.next();
int key=entry.getKey();
int value=entry.getValue();
System.out.println(key+" "+value);
}
有了如上的基础之后，因为我们的Collections.sort接收list类型的数据，所以我们在定义完成之后，就可以使用其进行对Value值的降序或者是升序的排列：
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o2.getValue()-o1.getValue();// 表示降序排列
return o1.getValue()-o2.getValue();// 表示升序排列
}
});
扩展
当然这里对于Map中的数值接收的是int类型，但是有时候我们并不想对Map中的类型进行写死，想根据，输入的值的不同，进行不同的排序处理：
public static <K, V extends Comparable<? super V>> Map<K, V> SortedMap(Map<K, V> map) {
List<Map.Entry<K, V>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
@Override
public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
return o1.getValue()-o2.getValue();// 升序
return o2.getValue()-o1.getValue();// 降序
}
});
Map<K, V> returnMap = new LinkedHashMap<K, V>();
for (Map.Entry<K, V> entry : list) {
returnMap.put(entry.getKey(), entry.getValue());
}
return returnMap;
}
测试
int类型数据
测试数据：
Map map = new HashMap<>();
map.put("Tom",2);
map.put("Jack",1);
map.put("sun",4);
map.put("star",21);
System.out.println("排序前--->" + map);
System.out.println("----------------");
map = SortedMap(map);
System.out.println("排序后--->" + map);
测试结果：
排序前--->{Tom=2, star=21, Jack=1, sun=4}
----------------
排序后--->{star=21, sun=4, Tom=2, Jack=1}
String类型数据
测试数据：
Map map = new HashMap<>();
map.put("Tom","azc");
map.put("Jack","bac");
map.put("sun","bzc");
map.put("star","abc");
System.out.println("排序前--->" + map);
System.out.println("----------------");
map = SortedMap(map);
System.out.println("排序后--->" + map);
测试结果：
排序前--->{Tom=azc, star=abc, Jack=bac, sun=bzc}
----------------
排序后--->{sun=bzc, Jack=bac, Tom=azc, star=abc}
对Key排序
在完成了对Value的排序以后来进行系列的对Key值的排序处理。对于Key值的排序就比较容易实现了。
public static <K, V extends Comparable<? super V>> Map<K, V> SortedKey(Map<K,V> map){
K [] key = (K[]) map.keySet().toArray();
Arrays.sort(key);
Map<K,V> returnMap = new LinkedHashMap<>();
for(K keys : key){
returnMap.put(keys,map.get(keys));
}
return returnMap;
}
测试
String类型数据
测试数据：
Map<String, String> map = new LinkedHashMap<>();
map.put("azc", "a");
map.put("abc", "b");
map.put("bzc", "d");
map.put("bac", "e");
System.out.println("排序前--->" + map);
System.out.println("----------------");
map = SortedKey(map);
System.out.println("排序后--->" + map);
测试结果：
排序前--->{azc=a, abc=b, bzc=d, bac=e}
----------------
排序后--->{abc=b, azc=a, bac=e, bzc=d}
