如何提高算法性能的速度來計算最小移動次數？

-1

我參加codefights並讓任務找到從輸入中獲得嚴格遞增序列所需的最少移動次數。作爲一個輸入，有整數數組，並且按照規則，我可以每移動一個數組，增加一個數組。如何提高算法性能的速度來計算最小移動次數？

inputArray: [1, 1, 1] 
Expected Output:3 

inputArray: [-1000, 0, -2, 0] 
Expected Output:5 

inputArray: [2, 1, 10, 1] 
Expected Output:12 

inputArray: [2, 3, 3, 5, 5, 5, 4, 12, 12, 10, 15] 
Expected Output:13

也有輸入和輸出條件：

[time limit] 4000ms (py3) 
[input] array.integer inputArray 
3 ≤ inputArray.length ≤ 105, 
-105 ≤ inputArray[i] ≤ 105 
[output] integer

我與followitn解決方案上來：

def arrayChange(inputArray): 
k=0 
for i in range(len(inputArray)-1): 
    if (inputArray[i]<inputArray[i+1]) == False: 
     while inputArray[i+1]<=inputArray[i]: 
      inputArray[i+1] = inputArray[i+1] + 1 
      k +=1 
return k

然而，apperantly對於一些測試，我不能看到我的算法性能超出時間限制：

6/8 測試7超出執行時間限制：程序超出執行時間限制。確保它在幾秒鐘內完成執行任何可能的輸入。樣品測試：4/4 隱藏測試：2/4

如何提高我的提高性能速度的算法？

來源

2017-05-18 user21

現在你每次增加1。目前，你有這樣的代碼片段：

inputArray[i+1] = inputArray[i+1] + 1

，而不是由1每次遞增，爲什麼不一次添加所有的號碼的？例如，如果您有列表[1, 3, 0]，則將最後一個元素添加4是有意義的。這樣做比添加1 4次要快得多。

來源

2017-05-18 22:57:51 fileyfood500

@ fileyfood500給了我一個非常有用的提示，這裏是我的解決方案，它的工作原理：

deltX=0 
for i in range(len(a)-1): 
    if (a[i]<a[i+1]) == False: 
     deltX1 = abs(a[i+1]-a[i])+1 
     a[i+1] = a[i+1] + deltX1 
     deltX += deltX1 
print(deltX)

現在我並不需要做while循環，因爲在所有我增加的項目，應在增加必要的數一步。

來源

2017-05-19 09:42:42 user21

def arrayChange(inputArray): 
    count = 0 
    for i in range(1,len(inputArray)): 
     while inputArray[i] <= inputArray[i-1]: 
      c = inputArray[i] 
      inputArray[i]= inputArray[i-1]+1 
      count += inputArray[i] - c 
    return count

這樣你直接增加它，時間會更少。
然後，只需從較早的值中減去新值以獲取其增量的次數。

來源

2018-02-05 13:32:50

如何提高算法性能的速度來計算最小移動次數？

回答

相關問題