Find K-th largest element in an array.
Have you met this question in a real interview?
Yes
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
You can swap elements in the array
Challenge
O(n) time, O(1) extra memory.
Tags Expand
Related Problems Expand
class Solution { //param k : description of k //param numbers : array of numbers //return: description of return public int kthLargestElement(int k, ArrayList<Integer> numbers) { // write your code here PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k); for(Integer num: numbers){ if(queue.size()<k){ queue.add(num); } else if(queue.peek() < num){ queue.remove(); queue.add(num); } } return queue.peek(); } };