本文主要是介绍[leetcode215][c++实现]数组中的第K个最大元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
记录下面试高频题，数组中的第K个最大元素。
这里记录用最大堆的解法，思路应为：构建一个最大堆，弹出堆顶元素，然后最大堆会自动维护，重复k次过程，就可以得到第K大的元素。
时间复杂度分析：构建最大堆：O(n),删除k个：O（klogn）。
首先记录一版调用api的代码
#include <iostream>
#include <string>
#include <set>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
//string a max length string
void print_vec(vector<int> num){for(auto i:num)cout << i << " " ;cout << endl;
}
int main(int argc, const char * argv[]) {vector<int> input_num{7,8,4,24,12,53}; //inputprint_vec(input_num); //printint k;cin >> k;cout << "需要弹出第K大的元素：" << endl;make_heap(input_num.begin(), input_num.end(), less<int>()); //build a maxHeapwhile(k--){pop_heap(input_num.begin(), input_num.end(), less<int>()); //delete the top nodeif(k!=0){input_num.pop_back(); // pop the num in the vector}else{cout << "第k大的数:" << input_num.back() << endl;input_num.pop_back();}}print_vec(input_num);return 0;
}
首先，make_heap用来构建一个最大堆，pop_heap用来删除堆顶的节点，此时节点会被放在vector容器的末尾，用pop_back()彻底删除此节点。
下面记录一下手写堆api的代码。
void print_vec(vector<int> num){for(auto i:num)cout << i << " " ;cout << endl;
}
void check_maxHeap(vector<int> &num,int i){int child_left = i*2+1;int child_right = (i+1)*2;int largest_index = i;if(child_left<num.size() && num[largest_index]<num[child_left]){largest_index = child_left;}if(child_right<num.size() && num[largest_index]<num[child_right]){largest_index = child_right;}if (largest_index!=i) {swap(num[largest_index], num[i]);check_maxHeap(num, largest_index);}
}
void init_maxHeap(vector<int> &num){for(int i=num.size()/2;i>0;i--){check_maxHeap(num, i);}
}
void pop_heap(vector<int> &num){swap(num[0],num[num.size()-1]);num.pop_back();check_maxHeap(num, 0);
}int main(int argc, const char * argv[]) {vector<int> input_num{7,8,4,24,12,53};print_vec(input_num);int k;cin >> k;cout << "需要弹出第K大的元素：" << endl;init_maxHeap(input_num);while(k--){if(k!=0){pop_heap(input_num);}else{cout << "第k大的数:" << input_num.back() << endl;pop_heap(input_num);}}print_vec(input_num);return 0;
}从上到下调整节点，当遇到一个非叶子节点的时候，检查孩子节点与其的大小关系（check_maxheap函数），如果这时需要交换节点，则需要递归检查其交换的子节点（是否还保持平衡）。
每次删除堆顶元素的时候，将末尾的节点与其交换，在用vector来删除末尾的元素，同时检查平衡。
参考资料：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
这篇关于[leetcode215][c++实现]数组中的第K个最大元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
