主页 数组中的第K个最大元素
Post
Cancel

数组中的第K个最大元素

前言

本文具有强烈的个人感情色彩,如有观看不适,请尽快关闭. 本文仅作为个人学习记录使用,也欢迎在许可协议范围内转载或分享,请尊重版权并且保留原文链接,谢谢您的理解合作. 如果您觉得本站对您能有帮助,您可以使用RSS方式订阅本站,感谢支持!

如题

给定整数数组nums和整数k,请返回数组中第k个最大的元素。

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

示例1

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

示例2

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

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
   void maxHeapify(vector<int> &nums, int i, int heapsize) {
        int left = i * 2+1, right = i * 2+2, largest = i;
        if (left < heapsize && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapsize && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(nums[i], nums[largest]);
            maxHeapify(nums, largest, heapsize);
        }
    }

    void buildMaxHeap(vector<int> &nums, int heapsize){
        for (int i = heapsize/2; i >= 0; --i) {
            maxHeapify(nums, i , heapsize);
        }
    }

    //堆化
    int findKthLargest(vector<int> nums, int k){
        int heapsize = nums.size();
        buildMaxHeap(nums, heapsize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0],nums[i]);
            --heapsize;
            maxHeapify(nums, 0, heapsize);
        }
        return nums[0];
    }
};

215. 数组中的第K个最大元素
引用自codetop

该博客文章由作者通过 CC BY 4.0 进行授权。

LRU 缓存

三数之和