算法面试——堆与优先队列：前K个高频元素、合并K个链表、数据流中位数

堆优先队列常用于需要反复获取最大/最小值的场景。Java 中用 PriorityQueue。一、前 K 个高频元素publicint[]topKFrequent(int[]nums,intk){MapInteger,IntegerfreqnewHashMap();for(intnum:nums)freq.put(num,freq.getOrDefault(num,0)1);// 小顶堆保留频率最高的 k 个PriorityQueueIntegerpqnewPriorityQueue((a,b)-freq.get(a)-freq.get(b));for(intkey:freq.keySet()){pq.offer(key);if(pq.size()k)pq.poll();}int[]resultnewint[k];for(intik-1;i0;i--)result[i]pq.poll();returnresult;}二、合并 K 个升序链表publicListNodemergeKLists(ListNode[]lists){PriorityQueueListNodepqnewPriorityQueue((a,b)-a.val-b.val);for(ListNodenode:lists){if(node!null)pq.offer(node);}ListNodedummynewListNode(0);ListNodecurdummy;while(!pq.isEmpty()){ListNodenodepq.poll();cur.nextnode;curcur.next;if(node.next!null)pq.offer(node.next);}returndummy.next;}三、数据流中位数classMedianFinder{privatePriorityQueueIntegermaxHeap;// 左半部分大顶堆privatePriorityQueueIntegerminHeap;// 右半部分小顶堆publicMedianFinder(){maxHeapnewPriorityQueue((a,b)-b-a);minHeapnewPriorityQueue();}publicvoidaddNum(intnum){if(maxHeap.isEmpty()||nummaxHeap.peek()){maxHeap.offer(num);}else{minHeap.offer(num);}// 平衡两个堆的大小if(maxHeap.size()minHeap.size()1){minHeap.offer(maxHeap.poll());}elseif(minHeap.size()maxHeap.size()){maxHeap.offer(minHeap.poll());}}publicdoublefindMedian(){if(maxHeap.size()minHeap.size()){returnmaxHeap.peek();}return(maxHeap.peek()minHeap.peek())/2.0;}} 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/MySQL 实战干货不让你白来。