LeetCode每日一题：数组中的第K个最大元素

传送门

题目要求在一个无序数组中找到第K大的元素，不能使用排序。

最开始的想法是借用冒泡的思想两重循环去枚举，但是显然会超时，于是想到了二叉堆。

题目要求输出第K大，那么只需要在原数组上构建一个二叉堆，然后执行k-1次删除操作，堆顶即使答案。

class Solution {
public:
    void update(vector<int>& arr, int i, int maxSize)
    {
        int maxn = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;

        if (left < maxSize && arr[left] > arr[maxn])
        {
            maxn = left;
        }

        if (right < maxSize && arr[right] > arr[maxn])
        {
            maxn = right;
        }

        if (maxn != i)
        {
            swap(arr[i], arr[maxn]);
            update(arr, maxn, maxSize);
        }
    }

    void buildHeap(vector<int>& arr, int maxSize)
    {
        for(int i = maxSize/2; i >= 0; i--)
        {
            update(arr, i, maxSize);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        int maxSize = nums.size();

        buildHeap(nums, maxSize);

        for(int i = nums.size()-1; i >= nums.size()-k+1; i--)
        {
            swap(nums[0], nums[i]);
            maxSize--;
            update(nums, 0, maxSize);
        }

        return nums[0];
    }
};