c++ - 由于 Hackerrank 中的超时而终止(在 cpp 中使用 malloc)
问题描述
所以我是一个相当新的程序员,我刚刚开始在 Hackerrank 上做题。我尝试了一个问题,它可以在离线 ide 上编译和工作。但是在hackerrank上显示错误。一个及时的回答真的会帮助我。
这是素数螺旋的虚拟表示(用于理解目的)
现在的问题 素数以螺旋形式书写,从原点 (0, 0) 开始,如上图所示移动。右列和底行显示的数字分别是列号和行号(即y和x坐标)
目标是找到给定素数的位置(x 和 y 坐标)。
错误 当我在hackerrank 中运行代码时,3 个测试用例中的2 个有效。但是对于一个测试用例,它显示错误因超时而终止。我写的代码如下:
#include<iostream>
using namespace std;
int prime(int a)
{
int count, h=0;
for (int i = 2; i <= 12000000; i++)
{
count = 0;
for (int j = 2; j <= i; j++)
{
if(i%j==0)
{
count++;
}
}
if (count == 1)
{
h = h + 1;
}
if (a == i)
{
break;
}
}
return h;
}
void spiral(int h)
{
int stepnum=1, totalsteps = 2;
int x_coordinate = 0, y_coordinate = 0;
int operatn = 1;
for(int i=2;i<=h;i++)
{
if (stepnum <= (totalsteps/2))
{
x_coordinate = x_coordinate + operatn;
}
else
{
if (stepnum <= totalsteps)
{
y_coordinate = y_coordinate + operatn;
}
}
if (stepnum == totalsteps)
{
stepnum = 0;
operatn = -1 * operatn;
totalsteps = totalsteps + 2;
}
stepnum++;
}
cout << "x coordinate = "<<x_coordinate<< " y coordinate = "<<y_coordinate<<endl;
}
int main()
{
int t;
int* p;
cout<<"Enter the number of cases :"<< endl;
cin >> t;
int test;
p=(int*)malloc(t*4);
for (int i = 0; i < t; i++)
{
cin >> *(p+i);
}
for (int i = 0; i < t; i++)
{
test = prime(*(p + i));
spiral(test);
}
}
解决方案
你的问题是这个循环:
for (int i = 2; i <= 12000000; i++)
...
for (int j = 2; j <= i; j++)
...
你最终会按照你的内循环的 n^2 次迭代的顺序进行,其中 n=12000000,所以你的内循环是 144*10^12 次迭代。
假设每次迭代需要 1 纳秒(实际上会更长),因此调用prime
完成需要 144*10^12 / 10^9 = 144000 秒,或约 1.7 天,除非您中断if (a == i)
.
因此,如果您的测试用例碰巧以prime
较大的 . 调用,a
则可能会超出分配的时间预算。
推荐阅读
- node.js - 用于返回特定日期范围的按日计数的 MongoDB 聚合函数
- html - 如何在 ABAP 中编写 HTML 代码来发送邮件
- scala - Akka,通用 ActorRef?
- php - 每下一个数字递增数字php
- selenium-webdriver - 测试注释代码不工作,只是 BeforeMethod 工作
- titanium - LiveView 与事件服务器断开连接
- javascript - 如何扩展缩短的 p 标签文本取决于下一个 p 标签?
- java - addValueEventListener 不能与过滤器一起使用或单独使用
- matlab - 如何创建调用句柄对象的uicontrol对象的回调函数
- arrays - 通过从多个输入字段(文本框)获取值来附加数组