[LintCode] Kth Largest Element [PriorityQueue]

Hwg 发布于2019-08-14 15:12 / 3024人阅读

摘要：可以不要用太简单的方法。先把它装满，再和队列顶端的数字比较，大的就替换掉，小的就。遍历完所有元素之后，顶部的数就是第大的数。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.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 数组中第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