c - 优化数组的双重迭代

Question

我有以下代码，是我为编码竞赛中的练习问题编写的，但是当我运行它时，我会超时。主要的罪魁祸首(我猜)是运行时间为 O(n^2) 的双 for 循环。有什么办法可以优化这段代码吗？我尝试过搞乱内存，但我不知道该怎么做。

for (i=n;i>0;i--){
    int index = linearSearch(seq,i,n);
    int height = bricks[index];
    for (j=0;j<n;j++){
        if (j != index){
            if (bricks[j] >= height){
                while(bricks[j]>=height){
                    bricks[j]--;
                    count++;
                }

                if(bricks[j] < 0){
                    printf("-1\n");
                    return 0;
                }

            }
        }
    }

    bricks[index] = 0;
    seq[index] = 0;
}

Answer 1

我不确定发布的代码片段的目标，但以下建议的代码可能有助于缩短执行时间:

for ( i=n; i>0; i-- )
{
    int index  = linearSearch(seq,i,n);
    int height = bricks[index];

    for ( j=0; j<n ; j++ )
    {
        if( j != index )
        {
            if( bricks[j] >= height )
            {
                count += bricks[j] - height;
                bricks[j] -= bricks[j] - height;
            }
        }
    }

    bricks[index] = 0;
    seq[index] = 0;
}