c - 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首先文章介绍如何计算算法的复杂度，因为它提供了非常有用的信息，并通过实际示例进行了解释。

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

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