資訊專(zhuān)欄INFORMATION COLUMN
摘要：可以不要用太簡(jiǎn)單的方法。先把它裝滿(mǎn)，再和隊(duì)列頂端的數(shù)字比較，大的就替換掉，小的就。遍歷完所有元素之后，頂部的數(shù)就是第大的數(shù)。
Problem
Find K-th largest element in an array.
ExampleIn 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.
可以不要用太簡(jiǎn)單的方法。
什么和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).
做一個(gè)大小為k的PriorityQueue，peek()到的最頂端元素是隊(duì)列中最小的元素，那么PQ就像一個(gè)自動(dòng)過(guò)濾掉比頂端元素更小元素并把內(nèi)部所有元素進(jìn)行排序的容器。先把它裝滿(mǎn)，再和隊(duì)列頂端的數(shù)字比較，大的就替換掉，小的就continue。遍歷完所有元素之后，頂部的數(shù)就是第k大的數(shù)。
熟悉PriorityQueue的操作，.add(), .peek(), .remove().
1.
class Solution {
public int kthLargestElement(int k, int[] nums) {
Arrays.sort(nums);
int len = nums.length;
return nums[len - k];
}
}
2.
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();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65460.html
摘要：解題思路，默認(rèn)就是隊(duì)列頂端是最小元素，第大元素，我們只要限制的大小為即可，最后隊(duì)列頂端的就是第大元素。代碼解題思路利用存入，之后采用，并限制最多放個(gè)元素。 Kth Largest Element in an ArrayFind the kth largest element in an unsorted array. Note that it is the kth largest el...
摘要：優(yōu)先隊(duì)列復(fù)雜度時(shí)間空間思路遍歷數(shù)組時(shí)將數(shù)字加入優(yōu)先隊(duì)列堆，一旦堆的大小大于就將堆頂元素去除，確保堆的大小為。如果這個(gè)分界點(diǎn)是，說(shuō)明分界點(diǎn)的數(shù)就是第個(gè)數(shù)。 Kth Largest Element in an Array Find the kth largest element in an unsorted array. Note that it is the kth largest e...
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...
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...
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 { ...
閱讀 2207·2023-04-25 14:50
閱讀 2964·2021-11-17 09:33
閱讀 2679·2019-08-30 13:07
閱讀 2913·2019-08-29 16:57
閱讀 975·2019-08-29 15:26
閱讀 3623·2019-08-29 13:08
閱讀 2059·2019-08-29 12:32
閱讀 3467·2019-08-26 13:57
