第一題: 第 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;
    }