배열이 주어지고 그것에 대해 삽입 정렬을 수행하도록 요청받았다고 가정합니다. 삽입 정렬에서 배열의 각 요소는 배열의 올바른 위치로 이동합니다. 배열을 정렬하는 데 필요한 총 이동 수를 찾아야 합니다. 총 이동 횟수는 정수이며 배열이 이미 정렬되어 있으면 0을 반환합니다.
따라서 입력이 input_array =[4, 5, 3, 1, 2]와 같으면 출력은 8
이 됩니다.[4, 5, 3, 1, 2] = 0 shifts [4, 5, 3, 1, 2] = 0 shifts [3, 4, 5, 1, 2] = 2 shifts [1, 3, 4, 5, 2] = 3 shifts [1, 2, 3, 4, 5] = 3 shifts
총 이동 수는 =0 + 0 + 2 + 3 + 3 =8입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 길이 :=input_arr의 크기
- temp_arr :=0으로 초기화된 크기 1000001의 새 목록
- ans :=0
- input_arr의 각 항목에 대해 다음을 수행합니다.
- val :=항목
- val> 0일 때 수행
- ans :=ans + temp_arr[val]
- val :=val - (val AND -val)
- val :=항목
- val <=1000000인 동안 do
- temp_arr[val] :=temp_arr[val] + 1
- val :=val + (val AND -val)
- ans :=length * ((length - 1) / 2의 바닥 값) - ans
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(input_arr): length = len(input_arr) temp_arr = [0] * 1000001 ans = 0 for item in input_arr: val = item while val > 0: ans += temp_arr[val] val -= val & -val val = item while val <= 1000000: temp_arr[val] = temp_arr[val] + 1 val += val & -val ans = length * (length - 1) // 2 - ans return ans print(solve([4, 5, 3, 1, 2]))
입력
[4, 5, 3, 1, 2]
출력
8