LeetCode|LeetCode 215 数组中的第K个最大元素
215. 数组中的第K个最大元素
【LeetCode|LeetCode 215 数组中的第K个最大元素】这道题是找到数组中的第K个最大元素，里面有个陷阱就是惯性思维，一开始只简单的认为用数组嘛，这直接用桶排序不就完了，但自己真的太天真了。。。完全没想到数字还可以是负数啊，然后又干脆直接通过给数组的每个元素排序吧，那怎么输出呢？又不能按位置输出，因为可能其中包含重复的数字，那是要设置一个max值，然后每次得到数组中一个比max大的数就让另一个标记flag++吗 这也不行啊。
栈好像可以？每次得到一个栈中最大的数就让他出栈，等到出栈了k-1个大数之后，就对栈逆序，然后输出栈顶元素，但前提是栈中的元素需要排好大小，很麻烦啊，有没有更简单的做法呢，只需要创建，排序不用你管，那么只能是二叉树了，这就得用到堆。
思路就是创建一个小根堆，小根堆和小顶堆的概念又不一样，这是概念
然后再把原数组中的第K个元素之前的值给小根堆，让它自动排好序。
现在因为要求第K大的数字，那么需要比较的最少次数就是数组的size-k次。
那么就开始用数组的第k+1个元素开始和数组中的第一个元素比较大小，大的话，就直接让其入小根堆就好了.注意 这个小根堆始终由K个元素组成，当大于K个元素时，还要释放堆顶的元素。这个概念是保证首元素是第K个最大元素的关键。
依次循环后，堆就保留了前K个最大的元素，这样，堆顶的元素就是正确答案。
源代码如下：
class Solution {
public:
int findKthLargest(vector& nums, int k) {
vector minstack(k);
for (int i = 0;
i < k;
i++) {
minstack[i] = nums[i];
}
make_heap(minstack.begin(), minstack.end(), greater());
//创建小根堆
for (int i = k;
i < nums.size();
i++) {
if (nums[i] > minstack[0]) {
minstack.push_back(nums[i]);
push_heap(minstack.begin(), minstack.end(), greater());
}
if (minstack.size() > k) {
pop_heap(minstack.begin(), minstack.end(), greater());
minstack.pop_back();
}
}
return minstack[0];
}
};
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 数组常用方法一
- Java|Java基础——数组
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- JS常见数组操作补充
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- JS|JS 数组求和与数组求平均值