สมมติว่าเรามีรายการตัวเลขที่แตกต่างกัน เราต้องหาจำนวนสวอปขั้นต่ำที่จำเป็นในการจัดเรียงรายการตามลำดับที่เพิ่มขึ้น
ดังนั้น หากอินพุตเป็น nums =[3, 1, 7, 5] ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถสลับ 3 กับ 1 แล้ว 5 และ 7 ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- sort_seq :=เรียงลำดับรายการ nums
- ตาราง :=แผนที่ใหม่
- สำหรับแต่ละดัชนี i และค่า n เป็น nums ทำ
- ตาราง[n] :=ฉัน
- สลับ :=0
- สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
- n :=nums[i]
- s_n :=sort_seq[i]
- s_i :=ตาราง[s_n]
- ถ้า s_n ไม่เหมือนกับ n แล้ว
- สวอป :=สวอป + 1
- nums[s_i] :=n
- nums[i] :=s_n
- ตาราง[n] :=s_i
- ตาราง[s_n] :=ฉัน
- คืนสวอป
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
โค้ดตัวอย่าง
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
