Chương trình tìm số lượng hoán đổi cần thiết để sắp xếp một mảng trong Python

Giả sử, chúng ta có một mảng gọi là nums và chúng ta phải tìm số lượng hoán đổi cần thiết để sắp xếp các num theo thứ tự bất kỳ, tăng dần hoặc giảm dần.

Vì vậy, nếu đầu vào là nums =[2, 5, 6, 3, 4], thì đầu ra sẽ là 2 vì ban đầu nums có [2, 5, 6, 3, 4]. Nếu chúng ta hoán đổi số 6 và 4, mảng sẽ là [2,5,4,3,6]. Sau đó, nếu chúng ta hoán đổi số 5 và 3, mảng sẽ là [2,3,4,5,6]. Vì vậy, cần 2 lần hoán đổi để làm cho mảng được sắp xếp theo thứ tự tăng dần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm swap_count (). Điều này sẽ lấy input_arr
  • pos:=danh sách mới chứa các bộ giá trị (item_postion, item) cho từng mục trong input_arr
  • sắp xếp vị trí danh sách theo các mục trong input_arr
  • cnt:=0
  • đối với chỉ mục trong phạm vi 0 đến kích thước của input_arr, hãy thực hiện
    • while True, do
      • nếu pos [index, 0] giống với index, thì
        • thoát khỏi vòng lặp
      • nếu không,
        • cnt:=swap_count + 1
        • swap_index:=pos [index, 0]
        • hoán đổi các giá trị của (pos [index], pos [swap_index])
  • trả về cnt
• Từ hàm / phương thức chính, hãy thực hiện như sau -
  • trả về tối thiểu (swap_count (input_arr), swap_count (input_arr theo thứ tự ngược lại))

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def swap_count(input_arr):
   pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
   cnt = 0

   for index in range(len(input_arr)):
      while True:
         if (pos[index][0] == index):
            break
         else:
            cnt += 1
            swap_index = pos[index][0]
            pos[index], pos[swap_index] = pos[swap_index], pos[index]

   return cnt

def solve(input_arr):
   return min(swap_count(input_arr), swap_count(input_arr[::-1]))

nums = [2, 5, 6, 3, 4]
print(solve(nums))

Đầu vào

[2, 5, 6, 3, 4]

Đầu ra

2