LeetCode演算法題-Kth Largest Element in a Stream(Java實現)
這是悅樂書的第296 次更新,第315 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第164題(順位題號是703)。設計一個類來查詢流中第k個最大元素。請注意,它是排序順序中的第k個最大元素,而不是第k個不同元素。KthLargest類有一個構造方法,此構造方法有一個整數k和一個整數陣列nums兩個引數,它包含來自流的初始元素。對於方法KthLargest.add的每次呼叫,返回表示流中第k個最大元素的元素。例如:
int k = 3;
int [] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3,arr);
kthLargest.add(3); //返回4
kthLargest.add(5); //返回5
kthLargest.add(10); //返回5
kthLargest.add(9); //返回8
kthLargest.add(4); //返回8
注意:nums的長度大於等於0。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
直接解法。使用陣列,在add方法裡,首先將原陣列擴容,將新的元素新增進陣列中去,再對陣列排序,然後取出倒數第k個元素。期間,藉助工具類Arrays來實現陣列擴容和排序。
class KthLargest { int k; int[] nums; public KthLargest(int k, int[] nums) { this.k = k; this.nums = nums; } public int add(int val) { int[] temp = Arrays.copyOf(nums, nums.length+1); temp[temp.length-1] = val; Arrays.sort(temp); nums = temp; return temp[nums.length-k]; } } /** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */
03 第二種解法
使用優先佇列。優先佇列自帶排序演算法,在初始化時如果不指定排序方式,則預設以自然方式排序,優先佇列的頭就會是以自然排序為基礎的最小元素。因此,我們可以在初始化優先佇列時,就指定其大小為k,然後找出最大的前k個元素存入優先佇列,每次呼叫add方法時,就比較傳參val和佇列頭的大小,如果val比佇列頭大,就移除原佇列頭,將val作為新的佇列頭。
class KthLargest { int k; PriorityQueue<Integer> q; public KthLargest(int k, int[] nums) { this.k = k; q = new PriorityQueue<Integer>(k); for (int n : nums) { add(n); } } public int add(int val) { if (q.size() < k) { q.offer(val); } else if (q.peek() < val) { q.poll(); q.offer(val); } return q.peek(); } } /** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */
04 小結
演算法專題目前已日更超過四個月 ,演算法題文章164 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!