Hackerrank挑战超时

Question

嘿，我只是想解决一个关于 hackerrank 的挑战，但在某些测试用例中代码超时，我不知道为什么。 This is the challenge.

这是我的代码：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n, k, q; 
    scanf("%d %d %d",&n,&k,&q);
    int qs[q];
    int a[n];

    for(int i = 0; i < n; i++){
       scanf("%d", &a[i]);
    }


    for(int i = 0; i < q; i++){
        scanf("%d",&qs[i]);
    }

    int lastNbr = a[n-1];
    for(int i = 0; i < k; i++){
        lastNbr = a[n-1];
        for(int j = n - 1; j > -1; j--){
            a[j] = (j-1 >= 0) ? a[j-1] : lastNbr;
        }
    }

    for(int i = 0; i < q; i++){
        printf("%d\n", a[qs[i]]);
    }

    return 0;
}

Answer 1

好吧，让我们开始分析你的算法的时间复杂度：

你有 2 个嵌套的 for 循环，它们总是进行 n * k 操作，因为你旋转数组 k 次并且你需要 n 操作来进行旋转。

这是 O(n * k)，所以它是对最坏情况输入的 10^10 操作，这对于这项任务来说太多了。

请先阅读 this 关于如何计算算法复杂度的文章，因为它提供了非常有用的信息，并通过实际示例进行了解释。

现在，您必须重新考虑您的算法并获得更好的时间复杂度。我不会破坏你的解决方案，但我可以给你一个提示：认为你真的不需要以 1 为单位旋转数组 k 次，你可以只这样做一次 k 个单位。

希望这对您有所帮助，祝您顺利解决挑战！ :)

Answer 2

如果您查看您的代码，它是 o (n*k) 个解决方案。你可以在o(n)时间内解决。输入大小为 10 pow 5 这就是您收到超时错误的原因。 % 会在这里帮助你。

Hackerrank挑战超时

Hackerrank challenge timout

c

algorithm

timeout