ACM题目,
错误提示:Time Limit Exceeded.
希望指出如何修改代码可以通过测试
在二分法查找的时候,在else部分,不能直接break。需要继续向左查找。举个例子来说,输入的所有数据是10000个3,在找3的时候,你的代码在找到5000这个位置的时候就结束while循环了,后面还需要从0到5000遍历,仍然比较耗时。所以,在else部分,仍然需要按照二分法向左查找,以提升查找效率。
代码测试通过。
代码修改如下(我把你代码中的m和n的位置调整了):
#include <stdio.h>
#include <stdlib.h>
int main()
{
int m=0,n=0,i=0,j=0,ret;
int low,high,mid;
scanf("%d%d",&n,&m);
long* arr=(long*)malloc(sizeof(long)*n); //所有的数
long* brr=(long*)malloc(sizeof(long)*m);//待询问的数
for(i=0;i<n;i++)
scanf("%ld",&arr[i]);
for(i=0;i<m;i++)
scanf("%ld",&brr[i]);
//遍历所有待询问的数
for(i=0;i<m;i++)
{
//二分法查找
low = 0;
high = n-1;
mid = (low+high)/2;
ret = -1;
while(low<=high)
{
if(brr[i]<arr[mid])
high = mid-1;
else if(brr[i]>arr[mid])
low = mid+1;
else
{
ret = mid;
high = mid-1;//继续向左找
}
mid = (low+high)/2;
}
if(ret != -1)
printf("%d",ret+1);
else
printf("-1");
if(i<n-1)
printf(" "); //空格
}
return 0;
}
会二分法吗?这样会让程序快点
您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!错误提示 “Time Limit Exceeded” 通常表示程序运行时间超出了限制。这意味着程序在给定的时间内无法完成所需的计算。为了解决这个问题,需要优化您的代码。
优化算法复杂度: 优化算法复杂度是提高程序性能的最有效方法。
使用缓存: 使用缓存来存储已经计算过的值可以减少重复计算,加快程序运行。
优化循环: 循环是程序中消耗时间最多的部分。优化循环可以提高程序性能。