215 数组中的第K个最大元素

思路

java
堆，又称优先级队列，在逻辑上可以视为一棵完全二叉树，且满足每个节点的值小于等于（小根堆）其左右孩子节点的值。从0开始按层次遍历的方式对树的节点编号，则用数组定义小根堆即数组a中每个元素满足a[i]<=a[2i+1]&&a[i]<=a[2i+2]（如果节点i有孩子）。
可以维护一个大小为k的小根堆，比如初始时为前k个元素，遍历之后每一个元素
如果该元素大于堆顶元素：交换它们，调整堆否则：跳过
那么遍历完整个数组后，前k个元素为最大的k个元素组成的小根堆，后面部分都比前面部分小，返回堆顶元素即为答案

代码

#构造大小为 k 的小顶堆
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        #   构造大小为 k 的小顶堆
        heap = [x for x in nums[:k]]
        heapq.heapify(heap)
        n = len(nums)
        for i in range(k, n):
            if nums[i] > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, nums[i])
        return heap[0]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();//系统默认即为小根堆
        int i = 0;
        for(;i < k;i++)
            queue.add(nums[i]);//前k个元素建堆，也可以用offer
        for(;i < nums.length;i++)
            if(queue.peek()<nums[i]){//peek拿出堆顶元素比大小
                queue.poll();
                queue.add(nums[i]);//java中没有replace操作，拆分成两步
            }
        return queue.peek();
    }
}

692前K个高频单词

![2@M1P4CRII)4K%R$S93ESB.png

思路

1用哈希表存储单词出现频率, key是word, value是出现频率
2根据哈希表中的value进行排序, 分为两种情况:
value不相等时, 值大的排在前边
value相等时, 按照key的字典顺序从小到大
3排序完成后，即可输出前k个key

代码

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        m = {}
        for word in words:
            if word not in m:
                m[word] = 1
            else:
                m[word] += 1
        sorted_list = sorted(m.items(), key=lambda item: (-item[1], item[0]))
        return [item[0] for item in sorted_list][:k]

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> m = new HashMap<>();
        for(String word : words) m.put(word, m.getOrDefault(word, 0)+1);
        List<Map.Entry<String, Integer>> sorted_list = new ArrayList<>();
        m.entrySet().forEach(sorted_list::add);
        sorted_list.sort((e1, e2) -> {
            if(e1.getValue() != e2.getValue()) return e2.getValue()-e1.getValue();
            else return e1.getKey().compareTo(e2.getKey());
        });
        List<String> res = new ArrayList<>();
        for(int i = 0; i < k; i++) res.add(sorted_list.get(i).getKey());
        return res;
    }
}