[LintCode] Kth Largest Element [PriorityQueue]

Hwg 發(fā)布于2019-08-14 15:12 / 3066人閱讀

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

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就像一個自動過濾掉比頂端元素更小元素并把內(nèi)部所有元素進行排序的容器。先把它裝滿，再和隊列頂端的數(shù)字比較，大的就替換掉，小的就continue。遍歷完所有元素之后，頂部的數(shù)就是第k大的數(shù)。
熟悉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

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

轉載請注明本文地址：http://systransis.cn/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 數(shù)組中第K大元

摘要：優(yōu)先隊列復雜度時間空間思路遍歷數(shù)組時將數(shù)字加入優(yōu)先隊列堆，一旦堆的大小大于就將堆頂元素去除，確保堆的大小為。如果這個分界點是，說明分界點的數(shù)就是第個數(shù)。 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