LeetCode 数组中的第K个最大元素

在未排序的数组中找到第 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 ≤ 数组的长度。
思路分析：使用堆排序（大顶堆），每次将当前堆的最大值放入末端，然后缩小堆的大小。

class Solution {
public:
	int findKthLargest(vector<int>& nums, int k) {
		int numsSize = nums.size();
		int cnt = numsSize, begin;
		for ( ; cnt > numsSize - k; --cnt){
			int tempCnt = cnt;//当前堆的大小
			//将当前堆的最大值放入堆顶
			while (tempCnt > 1){
				begin = tempCnt / 2 - 1;//最后一个有子节点的下标
				if (nums[begin] < nums[begin * 2 + 1]){//与左子节点比较
					swap(nums[begin], nums[begin * 2 + 1]);
				}
				//首先需要判断右子节点的存在，然后比较大小
				if (tempCnt % 2 == 1 && nums[begin] < nums[begin * 2 + 2]){
					swap(nums[begin], nums[begin * 2 + 2]);
				}
				//根据堆的奇偶性，缩小堆得大小
				if (tempCnt % 2 == 0){
					tempCnt -= 1;
				}
				else{
					tempCnt -= 2;
				}
			}
			swap(nums[0], nums[cnt - 1]);//将堆顶放入堆尾
		}
		return nums[cnt];
	}
};

当然也可以使用算法库中的sort或者其他排序方法排序，然后取下标。