Hackerrank挑戰timout

-3

嘿，我只是想解決的hackerrank但在一些測試用例的代碼超時是一個挑戰，我不知道爲什麼。 This is the challenge。Hackerrank挑戰timout

這裏是我的代碼：

#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; 
}

來源

2016-11-08 Nimmi

那麼，正如你所寫：**你**正試圖解決它。如果**我們**做到了......就不公平了 - - 您有**具體**問題嗎？ – Olaf

祕密是你不需要旋轉數組; '％'操作符是你的朋友。 –

@Olaf我的意思是當我提交代碼時，大多數測試用例正在工作，但有些超時。如果你想給我一個提示，說明我的部分代碼發生超時，那將是非常好的。 :) – Nimmi

好吧，讓我們開始分析你的算法的時間複雜度：

你有嵌套的循環總是去n * k操作2，當你旋轉您的陣列k次，您需要n操作來進行旋轉。

這會作爲O(n * k)，所以它是關於10^10操作在最壞的情況下輸入，這對於這項任務來說太多了。

請先閱讀this一篇關於如何計算算法的複雜性，因爲它提供了非常有用的信息，並將其與實際的例子說明。

現在，你必須重新考慮你的算法，並獲得更好的時間複雜度。我不會解決寵你，但我可以給你一個提示：想想你並不真的需要通過1單元轉動你的陣列k倍，可以改爲由k單位做一次。

希望這會有所幫助，祝你好運解決的挑戰！ :)

來源

2016-11-08 17:19:33

請注意，部分挑戰是OP在規定的時間內完成執行 - 如果他/她不能那麼他/她失敗了。如果我們爲他/她回答，他們學到了什麼（除了要求幫助比學習自己更容易） – KevinDTimm

我沒有破壞解決方案，我只給了一個關於研究時間複雜性的提示和文章。也許他/他還沒有掌握所有這些知識，也不知道從哪裏開始學習。另外，如果你無法弄清問題的解決方案，你可以提出一個提示，你不會花費更多的時間。就我個人而言，我認爲在一個問題上思考時間過長，即使你在1-2周之後發現問題，它也會浪費很多時間。 –

@VladTarniceru非常感謝您的幫助。是的，我在這個算法的主題很新，所以我沒有太多的知識在這個領域，我也開始學習c。 – Nimmi

如果你看看你的代碼，它是O（n * k）的解決方案。你可以在o（n）時間內解決它。並且輸入大小是10 pow 5，這就是爲什麼你會得到超時錯誤。％會幫助你在這裏。

來源

2016-11-08 17:24:15 Malav

Hackerrank挑戰timout

回答

相關問題