新网站怎么做才会被收录,新网站排名优化怎么做,电商平台搭建,做个网站大约多少钱文章目录 1、Java中的堆结构2、leetcode215#xff1a;数组中的第K个最大元素3、leetcode692#xff1a;前K个高频单词 1、Java中的堆结构
PriorityQueue类取堆顶元素删除堆顶元素堆的元素个数遍历堆 2、leetcode215#xff1a;数组中的第K个最大元素 这题应该快排来解数组中的第K个最大元素3、leetcode692前K个高频单词 1、Java中的堆结构
PriorityQueue类取堆顶元素删除堆顶元素堆的元素个数遍历堆 2、leetcode215数组中的第K个最大元素 这题应该快排来解这里用堆仅做练习。用堆实现的思路将数组存入最大堆k1找第一大的元素则取堆顶元素k2找第二大的元素则删掉堆顶元素取最新的堆顶元素k3则删掉两次堆顶元素后取新的堆顶元素
public class P215 {public static int getKMax(int[] array, int k) {if (array null || array.length 0 || k 1){return Integer.MIN_VALUE;}PriorityQueueInteger maxHeap new PriorityQueue(Collections.reverseOrder());for (int i : array) {maxHeap.add(i);}while (k 1) {// 删掉前面第k-1大的所有元素maxHeap.poll();k--;}// 取出删掉后新的堆顶元素即第K大的元素return maxHeap.peek();}
}
测试
public class P215 {public static void main(String[] args) {int[] array {3, 2, 3, 1, 2, 4, 5, 5, 6};System.out.println(getKMax(array, 4));}
} 3、leetcode692前K个高频单词 本质是个统计次数的问题自然想到哈希表结构可用HashMap统计完后前k个、第K个则可考虑最大堆。不过题中要求次数相等时按照字母排序因此要自定义比较器的实现先比次数次数相等再按字母排序 如果要用最小堆实现应该将值最小的元素往堆顶放、同等次数的把字母靠后的往堆顶放 然后限制最小堆里元素的个数为k个当超出k时剔除堆顶元素因为堆顶元素最小我要的是前K大的。遍历map完成后从堆中循环取出堆顶数据此时得到的顺序是从小到大的再反转下即可return 这里用最小堆和最小堆分别来解决
public class P692 {/*** 统计每个单词出现的数量*/public static HashMapString, Integer stats(String[] array) {if (array null || array.length 0) {return null;}HashMapString, Integer statsMap new HashMap();for (String str : array) {// 判断下是否包含这个key不要直接map.get(str) 1// 没这个key时get返回nullnull 1会空指针if (!statsMap.containsKey(str)) {statsMap.put(str, 1);} else {statsMap.put(str, statsMap.get(str) 1);}}return statsMap;}/*** 用最小堆解题*/public static ListString calcKMaxByMinHeap(HashMapString, Integer map, Integer k) {PriorityQueueStrInfo minHeap new PriorityQueue(new ComparatorStrInfo() {Overridepublic int compare(StrInfo o1, StrInfo o2) {if (!o1.count.equals(o2.count)) {return o1.count - o2.count;} else {return o2.str.compareTo(o1.str);}}});map.forEach((str, count) - {// 将每一条统计数据入堆入堆时会按照上面的比较规则做成最小堆minHeap.add(new StrInfo(str, count));// 入堆后如果元素数量超过了k扔掉堆顶元素if (minHeap.size() k) {minHeap.poll();}});// 将堆中的k个单词放入结果集ListString result new ArrayList();while (!minHeap.isEmpty()) {result.add(minHeap.poll().str);}// 结果倒转按题目要求的顺序returnCollections.reverse(result);return result;}/*** 用最大堆解题*/public static ListString calcKMaxByMaxHeap(HashMapString, Integer map, Integer k) {PriorityQueueStrInfo maxHeap new PriorityQueue(new ComparatorStrInfo() {Overridepublic int compare(StrInfo o1, StrInfo o2) {if (!o1.count.equals(o2.count)) {return o2.count - o1.count;} else {return o1.str.compareTo(o2.str);}}});// 将每一条统计数据入堆入堆时会按照上面的比较规则做成最大堆map.forEach((str, count) - {maxHeap.add(new StrInfo(str, count));});// 取前k个堆顶元素即为前K个高频单词ListString result new ArrayList();while (k 0) {result.add(maxHeap.poll().str);k--;}return result;}
}class StrInfo {String str;Integer count;public StrInfo(String str, Integer count) {this.str str;this.count count;}
}
测试
public class P692 {public static void main(String[] args) {String[] array {i, love, leetcode, i, love, coding};System.out.println(calcKMaxByMinHeap(stats(array), 2));}
}
