資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢排序序列所需的交換次數
假設我們有一個包含不同數字的列表；我們必須找到按升序排序該列表所需的最小交換次數。
因此，如果輸入類似於 nums = [3, 1, 7, 5]，則輸出將為 2，因為我們可以交換 3 和 1，然後交換 5 和 7。
為了解決這個問題，我們將遵循以下步驟：
- sort_seq := 對列表 nums 進行排序
- table := 一個新的對映
- 對於nums中的每個索引 i 和值 n：
- table[n] := i
- swaps := 0
- 對於 i 從 0 到 nums 的大小：
- n := nums[i]
- s_n := sort_seq[i]
- s_i := table[s_n]
- 如果 s_n 不等於 n，則：
- swaps := swaps + 1
- nums[s_i] := n
- nums[i] := s_n
- table[n] := s_i
- table[s_n] := i
- 返回 swaps
讓我們看下面的實現來更好地理解。
示例程式碼
class Solution:
def solve(self, nums):
sort_seq = sorted(nums)
table = {}
for i, n in enumerate(nums):
table[n] = i
swaps = 0
for i in range(len(nums)):
n = nums[i]
s_n = sort_seq[i]
s_i = table[s_n]
if s_n != n:
swaps += 1
nums[s_i] = n
nums[i] = s_n
table[n] = s_i
table[s_n] = i
return swaps
ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))輸入
[3, 1, 7, 5]
輸出
2
更新於: 2020年11月25日
1K+ 次瀏覽
廣告