【Day 85 】2024-02-08 - 215. 数组中的第 K 个最大元素

[azl397985856]

215. 数组中的第 K 个最大元素

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

前置知识

• 堆
• 排序

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

[snmyj]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq;
        for(auto n:nums){
            if(pq.size()==k && pq.top() >= n)continue;
            if(pq.size()==k){
                pq.pop();
            }
            pq.push(n);
        }
        return pq.top();
    }
};

[snmyj]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq;
        for(auto n:nums){
            if(pq.size()==k && pq.top() >= n)continue;
            if(pq.size()==k){
                pq.pop();
            }
            pq.push(n);
        }
        return pq.top();
    }
};

[Junru281]

利用priority queue的data structure, 每次保留目前遍历过中最大的k个数字. 然后在iterate through整个array之后, 自然就留下了最大的k个数字.

之后利用优先队列的数据结构, 第一个是kth largest element.

思路参考题解

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i = 0; i< nums.length; i++){
            pq.add(nums[i]);
            if(pq.size()> k){
                pq.poll();
            }
        }
        return pq.peek();
    }
}

时间复杂度: O(n)? # n是nums.length

空间复杂度: O(n)

[adfvcdxv]

class Solution {
public:
int quickselect(vector &nums, int l, int r, int k) {
if (l == r)
return nums[k];
int partition = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < partition);
do j--; while (nums[j] > partition);
if (i < j)
swap(nums[i], nums[j]);
}
if (k <= j)return quickselect(nums, l, j, k);
else return quickselect(nums, j + 1, r, k);
}

int findKthLargest(vector<int> &nums, int k) {
    int n = nums.size();
    return quickselect(nums, 0, n - 1, n - k);
}

};

[Chloe-C11]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        min_heap = []
        for n in nums:
            if len(min_heap) < k:
                heapq.heappush(min_heap, n)
            else:
                heapq.heappush(min_heap, n)
                heapq.heappop(min_heap)
        print(min_heap)
        return min_heap[0]

[larscheng]

思路

大顶堆

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o1-o2);

        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size()>k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)