第一题: 第 K 个最小的素数分数

LeetCode 786 : 第 K 个最小的素数分数
描述:
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

解题思路:

1. 求第K个最小的素数分数,先建立一个大小为k的大根堆.
2. 然后遍历数组,让所有可能的分数遍历一次
3. 首先让k个元素放入到堆中,
4. 然后再遍历的时候,进行比较,小于堆顶元素的,出堆顶元素,然后入堆.
5. 等到遍历结束,堆顶元素就是要得到的元素.
6. 此题难点在于重写compare时如何进行比较,分数比较需要用到double,而return的是int.

代码实现:

class Solution {
    public static int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(k,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                double a1 = o1[0]*1.0 / o1[1];
                double a2 = o2[0]*1.0 / o2[1];
                int flg = 0;//用flg来返回
                if(a2 - a1 < 0) flg = -1;
                else if (a2 - a1 > 0) flg = 1;
                return flg;
            }
        });//大根堆.
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1 ; j < arr.length; j++) {
                if(priorityQueue.size() < k){
                    priorityQueue.offer(new int[]{arr[i],arr[j]});
                }else {
                    double top = priorityQueue.peek()[0] * 1.0 / priorityQueue.peek()[1];
                    double tmp = arr[i] * 1.0 / arr[j];
                    if(tmp < top){//这里的比较也要double.
                        priorityQueue.poll();
                        priorityQueue.offer(new int[]{arr[i],arr[j]});
                    }
                }
            }
        }
        return priorityQueue.peek();
    }
}

第二题: 数据流中的第 K 大元素

LeetCode 703 : 数据流中的第 K 大元素
描述:
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

解题思路:

1. 建立一个大小为k的小根堆.
2. add的时候,将val入队,如果堆没满直接入队,堆满了,需要判断之后再决定是否入队.
3. add的类型为int,返回直接返回堆顶元素即可.

代码实现:

class KthLargest {
    final PriorityQueue<Integer> priorityQueue;
    final int k ;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        priorityQueue = new PriorityQueue<>(this.k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int val:nums) {
            add(val);
        }
    }
    public int add(int val) {
        if(priorityQueue.size() < k){
            priorityQueue.offer(val);
        }else {
            if(val > priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.offer(val);
            }
        }
        return priorityQueue.peek();
    }
}

第三题: 前 K 个高频元素

LeetCode 347: 前 K 个高频元素
描述:
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

解题思路:

1. 使用map,key值为数组出现的数据,value值记录key出现的次数.
2. 使用优先级队列,构建一个大小为k的小根堆,比较的是value的大小.
3. map添加的数据是有序的,所以直接遍历map,让数据入队.
4. 当堆的大小 > k的时候,要弹出队顶元素,
5. 遍历结束后,堆中的数据就是所需数据.
6. 定义一个长度为k的数组,让key的值放入数组中即可.

代码实现:

public int[] topKFrequent(int[] nums, int k) {
        int[] arr = new int[k];//长度为k的数组arr
        Map<Integer,Integer> map = new HashMap<>();
        //map记录数据出现的次数 key是数据,value是次数
        for (int i:nums) {
            map.put(i,map.getOrDefault(i,0)+1);
        }
        Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
        PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue()-o2.getValue();//比较的是出现次数
            }
        });
        for (Map.Entry<Integer,Integer> entry:entrySet) {
            pq.offer(entry);//map是有序的,所以每次遍历只需要入队就可以了
            if(pq.size() > k){
                pq.poll();//堆大小>k 出队
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            arr[i] = pq.poll().getKey();
        }//将数据添加到数组arr中
        return arr;
    }