파이썬에서 시퀀스를 정렬하는 데 필요한 스왑 수를 찾는 프로그램

<시간/>

고유한 숫자 목록이 있다고 가정합니다. 목록을 오름차순으로 정렬하는 데 필요한 최소 스왑 수를 찾아야 합니다.

따라서 입력이 nums =[3, 1, 7, 5]와 같으면 출력은 2가 됩니다. 3과 1, 5와 7을 바꿀 수 있기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

sort_seq :=목록 번호 정렬
테이블:=새 지도
숫자 단위의 각 인덱스 i와 값 n에 대해 다음을 수행합니다.
- 테이블[n] :=나
스왑:=0
0~숫자 크기 범위의 i에 대해
- n :=숫자[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]