我正準備很快面試工作,並進行了一次實踐技術測試。我在問題上做得很好,除了這一個...在線進行了練習技術面試,,,我錯過了什麼?
問題的前提是:給定一個數組,找到大小爲「n」的數組的順序子集的最大差異。示例
input = [6,8,4,5,3,1,7], n=3
[6,8,4] = the biggest diff = 4 (8-4)
[8,4,5] = the biggest diff = 4 (8-4)
[4,5,3] = 2
[5,3,1] = 4
[3,1,7] = 6
Final return from function:6
輸入限制類似於:數組的長度將小於100k,n將小於數組的長度。 該功能必須在2秒內完成。
我最初在python中寫過這個,但只接收了3/6正確的測試用例,3個因時間限制而失敗,所以我重寫了C,希望獲得更好的性能。
int i,j;
int maxdiff = 0;
int localmax,localmin,localdiff;
for (i=0;i<v_length-d+1;i++){
localmax = v[i];
localmin = v[i];
localdiff = 0;
for(j=0;j<d;j++){
if(v[j+i] > localmax){
localmax = v[j+i];
}
if(v[j+i] < localmin){
localmin = v[j+i];
}
}
localdiff = localmax-localmin;
if(localdiff > maxdiff){
maxdiff = localdiff;
}
}
return maxdiff;
我試着運行這個,但結果相同。 3/6正確,3/6由於運行時間而失敗。
我在這裏錯過了什麼嗎?我意識到我循環遍歷數組ArraySize中的每個值n次,我可以以某種方式在我的腦海中形象化地看到它可能只循環一次數組,但似乎無法弄清楚如何。 有什麼建議嗎? 謝謝!
夢幻般的解決方案! +1 – 2014-09-07 21:57:31