各位朋友,请帮我看一下这个程序哪里导致了成了“Time Limit Exceeded”,感谢。
我的代码,如下:
#include<bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int> > q;
int main()
{
int n, k, m;
cin >> n >> k;
for(int i = 0; i < n; i++)
{
cin >> m;
q.push(m);
}
int i = 0;
while(!q.empty())
{
if(i == k)
{
cout << q.top();
return 0;
}
else if(i != k)
{
q.pop();
i++;
}
}
return 0;
}
感谢
题目是什么,输入是什么
TLE一般来说要么是算法不优化,要么是本身程序存在死循环
回答来自GPT:
这段程序的时间复杂度为O(nlogn),主要是由于每次pop操作都需要重新调整堆的结构,可以通过使用一个大小为k的最大堆来优化。
优化后的代码如下:
#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main()
{
int n, k, m;
cin >> n >> k;
for(int i = 0; i < n; i++)
{
cin >> m;
if(q.size() < k)
{
q.push(m);
}
else if(m < q.top())
{
q.pop();
q.push(m);
}
}
cout << q.top();
return 0;
}
这样,只需要维护一个大小为k的最大堆,每次将新的元素与堆顶元素比较,如果比堆顶元素小,则将堆顶元素弹出,将新元素插入堆中。这样可以保证堆中始终保存着最小的k个元素,最后输出堆顶元素即可。这样的时间复杂度为O(nlogk),可以有效地避免超时问题。