赞
踩
面试中,TopK是问得比较多的几个问题之一;
所谓topK问题就是:假如给你100万个数据,让你找到前10个最大的数据
思路一:对整体就行排序,输出前10个最大的元素;
思路二:也就是本文准备详细讲解的思路,使用 堆(heap)
假如需要找一组数据中前K个最大的元素,那么我们需要:
求一个数组当中前K个最小的元素为列:
相关解释在代码中以注释形式给出,大家注意查看:
import java.util.*; public class TopK { /** * 求数组当中的前K个最小的元素 * @param array * @param k * @return */ public static int[] topK(int[] array,int k){ //1.创建一个大小为k的大跟堆 PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); //2.遍历数组当中的元素,前K个元素放到队列当中 for (int i = 0; i < array.length; i++) { if (maxHeap.size()<k){ maxHeap.offer(array[i]); }else{ //3.从第k+1个元素开始,每个元素和堆顶元素进行比较 int top=maxHeap.peek(); if (top>array[i]){ //k+1之后的元素发现比top小的就进行入队操作 maxHeap.poll(); //先将此事堆顶元素出队 maxHeap.offer(array[i]); } } } int[] tmp=new int[k]; for (int i = 0; i < k; i++) { tmp[i]=maxHeap.poll(); } return tmp; }
题目:给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k
定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
解题思路 :
为了结合代码进行理解,相关核心思路在代码中以注释形式给出:
public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { //注意最后结果以顺序表形式再次放到一个顺序表中(嵌套) PriorityQueue<List<Integer>> maxHeap=new PriorityQueue<>(k, new Comparator<List<Integer>>() { @Override //因为要找的是最小的元素,所以创建为大根堆 public int compare(List<Integer> o1, List<Integer> o2) { return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1)); //要找的是和最小 } }); for (int i = 0; i < Math.min(nums1.length,k); i++) { for (int j = 0; j < Math.min(nums2.length,k); j++) { //因为数据给出时候已经是升序了,避免出现死循环导致超时,所以遍历时候取数组长度和K的最小值即可 if (maxHeap.size()<k){//将前K个数据放入到优先级队列中 (topK问题) List<Integer> tmpList=new ArrayList<>(); tmpList.add(nums1[i]); tmpList.add(nums2[j]); maxHeap.offer(tmpList); //注意数据放入是以顺序表形式 }else{//k+1个数据开始遍历 int top=maxHeap.peek().get(0)+maxHeap.peek().get(1);//取和 题目要求 if (top>nums1[i]+nums2[j]){//k+1之后的元素和发现比top小的就进行入队操作 maxHeap.poll(); //入队之前注意需要先将堆顶元素出队 List<Integer> tmpList=new ArrayList<>(); tmpList.add(nums1[i]); tmpList.add(nums2[j] ); maxHeap.offer(tmpList);//元素入队操作 } } } } List<List<Integer>> ret=new ArrayList<>();//将此时k个堆中的数据(顺序表)再次放到一个顺序表中 for (int i = 0; i < k && !maxHeap.isEmpty(); i++) { //防止出现空指针异常 maxHeap不能为空 ret.add(maxHeap.poll()); } return ret; //ret中存放的即为前K个最小和的数据 }
给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。
解题思路 :
为了结合代码进行理解,相关核心思路在代码中以注释形式给出:
public List<String> topKFrequent(String[] words, int k) { //1.先用map来统计每次单词出现的次数 HashMap<String,Integer> map=new HashMap<>(); for (String s:words) { if (map.get(s)==null){ map.put(s,1); }else { int val=map.get(s); map.put(s,val+1); } } //2.建立一个大小为K的小根堆 PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() { @Override //如果频率相同情况 根据后面需要逆置操作 我们需要先调整为大根堆 //防止逆置后出错 //根据单词出现的频率来调整为小根堆 public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { if (o1.getValue().compareTo(o2.getValue())==0){ return o2.getKey().compareTo(o1.getKey()); } return o1.getValue()-o2.getValue(); } }); //3.遍历map for (Map.Entry<String,Integer> entry:map.entrySet()) { if (minHeap.size()<k){ minHeap.offer(entry); }else { //说明堆中 已经放满了K个元素,需要看堆顶元素的数据和当前数据的大小关系 Map.Entry<String,Integer> top=minHeap.peek(); //判断频率表是否相同,如果相同,比较单词的大小,单词小的入堆 if (top.getValue().compareTo(entry.getValue())==0){ if (top.getKey().compareTo(entry.getKey())>0){ minHeap.poll(); minHeap.offer(entry); } }else { if (top.getValue().compareTo(entry.getValue())<0){ minHeap.poll(); minHeap.offer(entry); } } } } List<String> ret=new ArrayList<>(); for (int i = 0; i < k; i++) { Map.Entry<String,Integer> top=minHeap.poll(); ret.add(top.getKey()); } //因为从小根堆弹出的第一个是最小的 题目要求从大到小 //所以调用集合方法逆置 Collections.reverse(ret); return ret; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。