資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學Python程式：使用插入排序查詢排序陣列所需的交換次數
假設我們得到一個數組，並被要求對其執行插入排序。在插入排序中，陣列中的每個元素都被移到其在陣列中的正確位置。我們必須找出排序陣列所需的總交換次數。總交換次數是一個整數，如果陣列已經排序，則返回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。
為了解決這個問題，我們將遵循以下步驟：
- length := input_arr的大小
- temp_arr := 一個大小為1000001的新列表，初始化為0
- ans := 0
- 對於input_arr中的每個專案，執行
- val := item
- 當val > 0時，執行
- ans := ans + temp_arr[val]
- val := val - (val AND -val)
- val := item
- 當val <= 1000000時，執行
- temp_arr[val] := temp_arr[val] + 1
- val := val + (val AND -val)
- ans := length * (length - 1 的向下取整) - ans
- 返回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
更新於： 2021年10月9日
1K+ 次檢視
廣告