최소 이동 횟수 계산을 위해 알고리즘 성능 속도를 높이려면 어떻게해야합니까?

Question

나는 codefights에 참여하고 입력으로부터 엄격하게 증가하는 시퀀스를 얻기 위해 필요한 최소한의 이동 수를 찾는다. 입력에는 정수 배열이 있고 규칙에 따라 하나의 요소를 하나의 이동 당 하나씩 정확히 늘릴 수 있습니다. apperantly 내 알고리즘을 관찰 할 수없는 테스트를 위해, 그러나

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 

: 나는 followitn 솔루션을 함께했다

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

:

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 

입력 및 출력에 대한 조건도 있습니다 성능이 시간 제한을 벗어났습니다 :

6/8 테스트 실행 시간 제한을 초과했습니다. 7 : 프로그램이 실행 제한 시간을 초과했습니다. 가능한 입력에 대해 몇 초 만에 실행이 완료되는지 확인하십시오. 샘플 테스트 : 4/4 숨겨진 테스트 : 2/4

어떻게 성능 속도를 증가시키기위한 내 알고리즘을 개선하기 위해?

Answer 1

지금은 한 번에 1 씩 증가합니다. 현재이 코드를 가지고 :

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

대신 1마다 증가, 왜 한 번에 모든 숫자를 추가하지? 예를 들어, 목록이 [1, 3, 0] 인 경우 마지막 요소에 4를 추가하는 것이 좋습니다. 이렇게하면 1 4 번을 추가하는 것보다 훨씬 더 빨리 진행됩니다. fileyfood500 @

Answer 2

은 나에게 매우 유용한 힌트를주고 여기서 일하는 내 솔루션입니다 :

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) 

을 지금은 항목을 증가하기 때문에 루프가 전혀 그가에 필요한 수의 증가되어야하는 동안 필요하지 않은이 한 걸음.

Answer 3

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 

이렇게하면 직접 증가 시키므로 시간이 줄어 듭니다.
그런 다음 이전 값에서 새 값을 빼서 증가하는 횟수를 얻으십시오.