核心方案：构建最大堆
代码方案：
1.使用algorithm.h中的 make_heap, pop_heap,push_heap 等函数方案
最初的方案我在VC中调试是能够通过的，但是过不去牛客网的编译器，因为没有递归，所以肯定是数组越界的问题，估计是边界条件没找好？
但是真心不知道边界条件哪里出了问题。
后来发现问题所在是，当input不够k个数的时候返回的是什么（牛客网设定给我的样例应该是返回为空），input正好为k的时候又该什么样，还有k=0的时候是什么样，都需要考虑。
//最初的判断入口参数的代码
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()<=k){
sort(input.begin(),input.end());
return input;
}
//通过的代码
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int n=input.size();
if(n<k||k==0){
vector<int> max_heap;
return max_heap;
}else if(n==k){
sort(input.begin(),input.end());
return input;
}
vector<int> max_heap(k,0);
for(int i=0;i<k;i++){
max_heap[i]=input[i];
}
//use the first k elements of input to initialize max_heap
make_heap(max_heap.begin(),max_heap.end());
int i=k;
while(i<n){
if(input[i]<max_heap[0]){
pop_heap(max_heap.begin(),max_heap.end());
//max_heap[k-1]=input[i];
max_heap.pop_back();
max_heap.push_back(input[i]);
push_heap(max_heap.begin(),max_heap.end());
}
i++;
}
sort_heap(max_heap.begin(),max_heap.end());
return max_heap;
}
};
附：algorithm库中heap操作示例：
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#define CLASSFOO_VECTOR(type, name, ...) \
static const type name##_a[] = __VA_ARGS__; \
std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
namespace ClassFoo{
void MakeHeap_1() {
// 构造 vector 对象
CLASSFOO_VECTOR(int, foo, { 0, 6, 33, 8, 10, -2, 13 });
// 构造一个堆
std::make_heap(foo.begin(), foo.end());
// 打印 foo
std::copy(
foo.begin(),
foo.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// 从堆中弹出（最大）元素
std::pop_heap(foo.begin(), foo.end());
// 实际删除
foo.pop_back();
// 打印 foo
std::copy(
foo.begin(),
foo.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// 向堆中压入一个元素
// 先压入元素至向量末尾
foo.push_back(56);
// 压入堆中
std::push_heap(foo.begin(), foo.end());
// 打印 foo
std::copy(
foo.begin(),
foo.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// 排序
std::sort_heap(foo.begin(), foo.end());
// 打印 foo
std::copy(
foo.begin(),
foo.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
}
int main()
{
ClassFoo::MakeHeap_1();
return 0;
}
方案2，使用STL中的priority_queue
- 第一个元素总是容器所包含的元素中按特定的严格弱序排序规则排序后最大的一个
- priority_queue 的定义使得它类似一个堆（Heap），该堆只能获得它的最大堆元素（在 priority_queue 中即为队列头）。
- 默认最大堆
//优先队列的使用样例，默认是最大堆，一元谓词函数使用greater的话，top就是小的数
1. #include [<iostream>](http://classfoo.com/ccby/article/Yxj7ge)
2. #include [<queue>](http://classfoo.com/ccby/article/WdLxdR)
3. #include [<functional>](http://classfoo.com/ccby/article/Qz6HcH)
5. namespace ClassFoo {
6. using namespace std;
8. void PriorityQueueExample1() {
9. priority_queue<int,vector<int>,greater<int> > foo1;
10. priority_queue<int,vector<int> >foo2;
11. int a[]={1,3,4,2,5,0,6};
12. for(int i=0;i<7;i++)
13. {
14. foo1.push(a[i]);
15. foo2.push(a[i]);
16. }
17. cout<<"foo1:";
18. while(!foo1.empty())
19. {
20. cout<<foo1.top()<<" ";
21. foo1.pop();
22. }
23. cout << endl;
24. cout << "foo2:";
25. while(!foo2.empty())
26. {
27. cout<<foo2.top()<<" ";
28. foo2.pop();
29. }
30. cout << endl;
31. }
32. }
33. int main()
34. {
35. ClassFoo::PriorityQueueExample1();
36. return 0;
37. }
网友评论