- Kth Largest Element in an Array 难度 中等
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
相关企业
Facebook|122
字节跳动|18
亚马逊 Amazon|18
领英 LinkedIn|17
微软 Microsoft|8
相关标签
- Array
- Divide and Conquer
- Quickselect
- Sorting
- Heap (Priority Queue)
相似题目
- Wiggle Sort II 中等
- Top K Frequent Elements 中等
- Third Maximum Number 简单
- Kth Largest Element in a Stream 简单
- K Closest Points to Origin 中等
- Sort: Time O(nlogn); Space O(logn)
- Partition: Time O(n); Space O(logn)
- Priority Queue: O(nlogk); O(k)
- Heap: O(n + klogn); O(logn)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums = sorted(nums, reverse=True)
return nums[k-1]class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
numslen = len(nums)
if not nums or k < 1 or k > numslen:
return -1
# k largest == len-k+1 smallest
return self.partition(nums, 0, numslen - 1, numslen - k)
def partition(self, nums, start, end, k):
# it has been guranteed start <= k <= end
if start >= end:
return nums[k]
left = start
right = end
pivotvalue = nums[(start + end) // 2]
while left <= right:
while left <= right and nums[left] < pivotvalue:
left += 1
while left <= right and nums[right] > pivotvalue:
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# this also works
# self.partition(nums, start, right, k)
# self.partition(nums, left, end, k)
# faster than above one, not complete array need to be sorted, partial sorted is enough
if k <= right:
self.partition(nums, start, right, k)
if k >= left:
self.partition(nums, left, end, k)
return nums[k]class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
return -1;
}
return this.partition(nums, 0, nums.length-1, nums.length-k);
}
private int partition(int[] nums, int start, int end, int k){
if (start >= end){
return nums[k];
}
int left = start;
int right = end;
int pivotvalue = nums[(start + end) / 2];
while (left <= right){
while (left <= right && nums[left] < pivotvalue){
left ++;
}
while (left <= right && nums[right] > pivotvalue){
right --;
}
if (left <= right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left ++;
right --;
}
}
if (k <= right) {
return this.partition(nums, start, right, k);
}
if (k >= left) {
return this.partition(nums, left, end, k);
}
return nums[k];
}
}class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
if (nums.size() == 0 || k < 1 || k > nums.size()){
return -1;
}
return this->partition(nums, 0, nums.size()-1, nums.size()-k);
}
private:
int partition(vector<int>& nums, int start, int end, int k){
if (start >= end){
return nums[k];
}
int left = start, right = end;
int pivotvalue = nums[(start + end) / 2];
while (left <= right){
while (left <= right && nums[left] < pivotvalue){
left ++;
}
while (left <= right && nums[right] > pivotvalue){
right --;
}
if (left <= right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left ++;
right --;
}
}
if (k <= right) { return this->partition(nums, start, right, k); }
if (k >= left) { return this->partition(nums, left, end, k); }
return nums[k];
}
};func findKthLargest(nums []int, k int) int {
if (nums == nil || len(nums) == 0 || k < 1 || k > len(nums)){
return -1;
}
return partition(nums, 0, len(nums)-1, len(nums)-k);
}
func partition(nums []int, start int, end int, k int) int{
if (start >= end){
return nums[k];
}
left := start
right := end
pivotvalue := nums[(start + end) / 2]
for (left <= right){
for (left <= right && nums[left] < pivotvalue){
left ++;
}
for (left <= right && nums[right] > pivotvalue){
right --;
}
if (left <= right){
nums[left], nums[right] = nums[right], nums[left];
left ++;
right --;
}
}
if (k <= right) { return partition(nums, start, right, k); }
if (k >= left) { return partition(nums, left, end, k); }
return nums[k];
}Priority queue is an abstract data type. It has multiple ways to implement it. Java and cpp have built-in implementations for it.
(Python queue.PriorityQueue is for messages. Not for general Priority Queue here.)
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // init a pq
// ordered by natural order
for (int num: nums){
pq.offer(num); //insert and sort
if (pq.size() > k) {
pq.poll(); // rm head (smallest)
}
}
return pq.peek(); // get head (smallest)
}
}class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
if (nums.size() == 0 || k < 1 || k > nums.size()){
return -1;
}
std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // head/top is smallest
for (int i = 0; i < nums.size(); i ++){
pq.push(nums[i]); // insert and sort
if (pq.size() > k){
pq.pop();
}
}
return pq.top();
}
};Time O(n) for building heap. O(klogn) for deleting. Space O(logn) because of the recursively using space.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
numslen = len(nums)
if not nums or k < 1 or k > numslen:
return -1
import heapq
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heapq.heappop(heap) Go has a heap package but you still need to implement some function for it when using.
import "container/heap"
// heap asks for implementation of Len() Less() Swap() Push() Pop()
type myMinIntHeap []int
func (h myMinIntHeap) Len() int { return len(h) }
func (h myMinIntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h myMinIntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *myMinIntHeap) Push(x interface{}){
*h = append(*h, x.(int))
}
func (h *myMinIntHeap) Pop() interface{}{
old := *h
n := len(old)
lastelem := old[n-1]
*h = old[0 : n-1]
return lastelem;
}
func findKthLargest(nums []int, k int) int {
if (nums == nil || len(nums) == 0 || k < 1 || k > len(nums)){
return -1;
}
hp := &myMinIntHeap{}
heap.Init(hp)
for _, num := range nums {
heap.Push(hp, num)
if hp.Len() > k {
heap.Pop(hp)
}
}
return heap.Pop(hp).(int)
}