[LintCode] Kth Largest Element [PriorityQueue]

Hwg 發布于2019-08-14 15:12 / 3059人閱讀

摘要：可以不要用太簡單的方法。先把它裝滿，再和隊列頂端的數字比較，大的就替換掉，小的就。遍歷完所有元素之后，頂部的數就是第大的數。

Problem

Find K-th largest element in an array.

Example

In array [9,3,2,4,8], the 3rd largest element is 4.
In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

Note

可以不要用太簡單的方法。
什么和Arrays.sort()最接近？PriorityQueue.
An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
A priority queue does not permit null elements.
A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

做一個大小為k的PriorityQueue，peek()到的最頂端元素是隊列中最小的元素，那么PQ就像一個自動過濾掉比頂端元素更小元素并把內部所有元素進行排序的容器。先把它裝滿，再和隊列頂端的數字比較，大的就替換掉，小的就continue。遍歷完所有元素之后，頂部的數就是第k大的數。
熟悉PriorityQueue的操作，.add(), .peek(), .remove().

Solution

class Solution {
    public int kthLargestElement(int k, int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return nums[len - k];
    }
}

class Solution {
    public int kthLargestElement(int k, int[] nums) {
        PriorityQueue queue = new PriorityQueue(k);
        for (int num : nums) {
            if (queue.size() < k) {
                queue.add(num);
            } else if (queue.peek() < num) {
                queue.remove();
                queue.add(num);
            }
        }
        return queue.peek();
    }
}

云服務器 GPU云服務器 Kth Largest PriorityQueue LintCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65460.html

Kth Largest Element in an Array，Top K Frequent Ele

摘要：解題思路，默認就是隊列頂端是最小元素，第大元素，我們只要限制的大小為即可，最后隊列頂端的就是第大元素。代碼解題思路利用存入，之后采用，并限制最多放個元素。 Kth Largest Element in an ArrayFind the kth largest element in an unsorted array. Note that it is the kth largest el...

Tony_Zby 2019-08-16 10:27 評論0 收藏0
[Leetcode] Kth Largest Element in an Array 數組中第K大元

摘要：優先隊列復雜度時間空間思路遍歷數組時將數字加入優先隊列堆，一旦堆的大小大于就將堆頂元素去除，確保堆的大小為。如果這個分界點是，說明分界點的數就是第個數。 Kth Largest Element in an Array Find the kth largest element in an unsorted array. Note that it is the kth largest e...

Rocko 2019-08-14 12:26 評論0 收藏0
[LintCode] Kth Smallest Number in Sorted Matrix

Problem Find the kth smallest number in at row and column sorted matrix. Example Given k = 4 and a matrix: [ [1 ,5 ,7], [3 ,7 ,8], [4 ,8 ,9], ] return 5 Challenge O(k log n), n is the maximal n...

mgckid 2019-08-14 15:45 評論0 收藏0
[LintCode] Top k Largest Numbers II

Problem Implement a data structure, provide two interfaces: add(number). Add a new number in the data structure.topk(). Return the top k largest numbers in this data structure. k is given when we crea...

jindong 2019-08-15 14:23 評論0 收藏0
[LintCode] Top k Largest Numbers I

Problem Given an integer array, find the top k largest numbers in it. Example Given [3,10,1000,-99,4,100] and k = 3.Return [1000, 100, 10]. Tags Heap Priority Queue Solution public class Solution { ...

solocoder 2019-08-15 13:25 評論0 收藏0