Giả sử chúng ta có một danh sách các số phân biệt; chúng ta phải tìm số lượng hoán đổi tối thiểu cần thiết để sắp xếp danh sách theo thứ tự tăng dần.
Vì vậy, nếu đầu vào giống như nums =[3, 1, 7, 5], thì đầu ra sẽ là 2, vì chúng ta có thể hoán đổi 3 và 1, sau đó là 5 và 7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- sort_seq:=sắp xếp các số trong danh sách
- table:=a new map
- đối với mỗi chỉ số i và giá trị n trong nums, thực hiện
- bảng [n]:=i
- hoán đổi:=0
- đối với tôi trong phạm vi từ 0 đến kích thước là num, hãy thực hiện
- n:=nums [i]
- s_n:=sort_seq [i]
- s_i:=table [s_n]
- nếu s_n không giống với n, thì
- swaps:=swaps + 1
- nums [s_i]:=n
- nums [i]:=s_n
- bảng [n]:=s_i
- bảng [s_n]:=i
- trả lại hoán đổi
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Mã mẫu
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)) Đầu vào
[3, 1, 7, 5]
Đầu ra
2