Leetcode#215. Kth Largest Element in an Array

本文主要是介绍Leetcode#215. Kth Largest Element in an Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：找出数组中第 k 大的数

解题思路：（20180825更新）

思路一：k次冒泡排序，就找到了，复杂度O(k * n)
思路二：使用数组内容构建一个最大堆/最小堆，通过每次pop出堆顶后继续维护堆的结构，直到满足一定的次数（最大堆k-1次，最小堆size-k次），堆顶的元素就是第k大的数字，复杂度O(n + k * log(n))；
思路三：维护一个k大小的小顶堆，遍历数组，调整堆，最后堆顶元素就是第k大，复杂度O(k + (n-k) * log(k))；
思路四：利用快排的partition函数思想，选定一个数组内的值作为pivot，将小于pivot的数字放到pivot右边，大于等于pivot的数字放到pivot左边。接着判断两边数字的数量，如果左边的数量小于k个，说明第k大的数字存在于pivot及pivot右边的区域之内，对右半区执行partition函数；如果右边的数量小于k个，说明第k大的数字在pivot和pivot左边的区域之内，对左半区执行partition函数。直到左半区刚好有k-1个数，那么第k大的数就已经找到了。

//思路一
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//k次冒泡for(int i = 0; i < k; ++i){for(int j = 1; j < nums.size() - i; ++j){if(nums[j] < nums[j - 1])swap(nums[j], nums[j - 1]); }}return nums[nums.size() - k];}
};

//思路二
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//建一个最大堆make_heap(nums.begin(), nums.end());int ret;for(int i = 0; i < k; ++i){ret = nums.front();//第一个元素被移到最后面，剩下的元素继续维持最大堆pop_heap(nums.begin(), nums.end());//将最后一个元素出堆nums.pop_back();}//以上执行了k步，被取出来的数就是第 k 大的数return ret;}
};//思路二,不使用STL的函数建堆，自己建堆
class Solution {
public:void Adjust(vector<int> &nums, int i, int k){//调整为最大堆int j = 2 * i + 1;while(j < k){if(j + 1 < k && nums[j] < nums[j + 1])++j;if(nums[i] < nums[j])swap(nums[i], nums[j]);i = j;j = 2 * i + 1;}}void make_heap(vector<int> &nums, int k){for(int i = k/2 - 1; i >= 0; --i)Adjust(nums, i, k);}int findKthLargest(vector<int>& nums, int k) {//建一个最大堆make_heap(nums, nums.size());//int ret;for(int i = nums.size() - 1; i >= 0; --i){swap(nums[0], nums[i]);Adjust(nums, 0, i);}//以上执行了k步，被取出来的数就是第 k 大的数return nums[nums.size() - k];}
};

//思路三
class Solution {
public:void Adjust(vector<int> &nums, int i, int k){//调整为最小堆int j = 2 * i + 1;while(j < k){if(j + 1 < k && nums[j] > nums[j + 1])++j;if(nums[i] > nums[j])swap(nums[i], nums[j]);i = j;j = 2 * i + 1;}}void make_heap(vector<int> &nums, int k){for(int i = k/2 - 1; i >= 0; --i)Adjust(nums, i, k);}int findKthLargest(vector<int>& nums, int k) {make_heap(nums, k);for(int i = k; i < nums.size(); ++i) //从第k个元素起，比较{if(nums[i] > nums[0]){swap(nums[i], nums[0]);Adjust(nums, 0, k);     //注意这里调整的是前k个元素}}return nums[0];}
};

//思路四
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int low = 0, high = nums.size() - 1;while(low <= high){int i = low;int j = high;int pivot = nums[low];while(i <= j){while(i <= j && nums[i] >= pivot)i++;while(i <= j && nums[j] <= pivot)j--;if(i < j)swap(nums[i], nums[j]);}swap(nums[low], nums[j]);if(j == k - 1)return nums[j];else if(j < k - 1)low = j + 1;elsehigh = j - 1;}}
};