如何处理 C 语言中超出时间限制的错误?

Question

你负责你侄女生日的蛋糕，并决定蛋糕在她总年龄的每一年都有一支蜡烛。当她吹灭蜡烛时，她只能吹灭最高的蜡烛。你的任务是找出她可以成功吹灭多少根蜡烛。

例如，如果您的侄女即将满 4 岁，蛋糕将有 4 根高度为 4、4、1、3 的蜡烛，她将能够成功吹灭 2 根蜡烛，因为最高的蜡烛高度为 4，并且有 2 根这样的蜡烛。

Constraints:
Age must be greater than or equal to 1 and less than or equal to 100,000
Height of the candle must be greater than or equal to 1 and less than or equal to 100,00,000
Sample Input:
4
3 2 1 3
Sample Output:
2

我想出了这个问题的代码。但我只能解决两个测试用例。当输入非常大(年龄(时，它显示为错误消息"超出时间限制"。这是我的代码。

#include <stdio.h>
#define N 100000
int main(){
int n,i,j,cnt=1;
long long a[N],temp;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
}
for(i=0;i<n-1;i++){
for(j=i+1;j<n;j++){
if(a[i]<a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=1;i<n;i++){
if(a[i]==a[0]){
cnt++;
}
else{
break;
}
}
printf("%d",cnt);
}

我不是一个非常好的程序员。我是学生。我会很高兴得到你的帮助。

Answer 1

您的代码在 O(n^2( 运行时中运行，这对于许多问题来说都是多余的。

这是一个具有更快运行时 O(n( 的解决方案。我们只检查每个元素一次。

#include <stdio.h>
int main()
{
int n, a[1000000], i;
printf("enter number of candles: ");
scanf("%d", &n);
printf("enter the candle heights belown");
for (i=0; i<n; i++){
scanf("%d", &a[i]);
}
int maxnum = a[0], ans = 0;
for (i=0; i<n; i++){
if (a[i] == maxnum) ans++;
if (a[i] > maxnum){
maxnum = a[i];
ans = 1;
}
}
printf("answer: %d", ans);
}

由于 C 和 C++ 密切相关，如果有人觉得有帮助，我将在此处保留此解决方案的原始C++版本。

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, temp;
vector<int> a;
cout << "enter number of candles: ";
cin >> n;
cout << "enter the candle heights below" << endl;
for (int i=0; i<n; i++){
cin >> temp;
a.push_back(temp);
}

if (n == 0) cout << 0;
int i, maxnum = a[0], ans = 0;
for (i=0; i<n; i++){
if (a[i] == maxnum) ans++;
if (a[i] > maxnum){
maxnum = a[i];
ans = 1;
}
}
cout << "answer: " << ans;
}

提示：解决此问题的另一种方法是使用更快的排序算法，例如 - 合并排序/快速排序。它们都具有比您使用的更快的运行时间(气泡排序(。