错误提示:Time Limit Exceeded.希望指出如何修改代码可以通过测试

ACM题目,
错误提示:Time Limit Exceeded.
希望指出如何修改代码可以通过测试

img

img

在二分法查找的时候,在else部分,不能直接break。需要继续向左查找。举个例子来说,输入的所有数据是10000个3,在找3的时候,你的代码在找到5000这个位置的时候就结束while循环了,后面还需要从0到5000遍历,仍然比较耗时。所以,在else部分,仍然需要按照二分法向左查找,以提升查找效率。
代码测试通过。

img

代码修改如下(我把你代码中的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;
}

会二分法吗?这样会让程序快点

您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!
PS:问答VIP年卡 【限时加赠:IT技术图书免费领】,了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632

错误提示 “Time Limit Exceeded” 通常表示程序运行时间超出了限制。这意味着程序在给定的时间内无法完成所需的计算。为了解决这个问题,需要优化您的代码。

优化算法复杂度: 优化算法复杂度是提高程序性能的最有效方法。

使用缓存: 使用缓存来存储已经计算过的值可以减少重复计算,加快程序运行。

优化循环: 循环是程序中消耗时间最多的部分。优化循环可以提高程序性能。