Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서만 주어진 인덱스 간의 스왑을 사용하여 배열을 정렬할 수 있는지 확인

<시간/>

[0, n – 1] 범위의 고유한 값을 가진 num이라는 배열이 있다고 가정합니다. 이 배열은 정렬되지 않았습니다. 또한 각 쌍에 배열의 요소를 교환할 수 있는 인덱스가 포함된 또 다른 쌍의 배열이 있습니다. 여러 번 교환할 수 있습니다. 이러한 스왑을 사용하여 배열을 정렬된 순서로 정렬할 수 있는지 여부를 확인해야 합니다.

따라서 입력이 nums =[6,1,7,3,0,5,4,2] pair =[(0,4),(6,0),(2,7)]과 같으면 인덱스(2,7)를 스왑할 수 있으므로 출력은 True입니다. 배열은 [6,1,2,3,0,5,4,7]이 되고 스왑(6,0)은 배열이 [4, 1,2,3,0,5,6,7]을 선택한 다음 (0,4)를 교체하여 [0,1,2,3,4,5,6,7]을 얻습니다.

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

  • N :=숫자의 크기, P :=쌍 배열의 쌍 수
  • v :=N개의 하위 목록이 있는 목록
  • 방문함:=새로운 세트
  • 0에서 P 사이의 i에 대해 다음을 수행합니다.
    • 쌍의 두 번째 인덱스[i]를 v[쌍의 첫 번째 인덱스[i]]에 삽입
    • 쌍의 첫 번째 인덱스[i]를 v[쌍의 두 번째 인덱스[i]]에 삽입
  • 0~N 범위의 i에 대해 다음을 수행합니다.
    • 내가 방문하지 않으면
      • que :=이중 종료 대기열
      • arr_first :=새 목록
      • arr_second :=새 목록
      • 방문한 것으로 표시
      • que 끝에 i 삽입
      • que가 비어 있지 않은 동안 do
        • u :=que의 앞 요소 및 que의 앞 요소 삭제
        • arr_first의 끝에 u를 삽입
        • arr_second 끝에 nums[u] 삽입
        • v[u]의 각 s에 대해
          • s를 방문하지 않으면
            • 방문한 것으로 표시
            • queue 끝에 s 삽입
      • arr_first :=목록 정렬 arr_first
      • arr_second :=목록 정렬 arr_second
      • arr_first가 arr_second와 같지 않으면
        • 거짓을 반환
  • 참 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시 코드

from collections import deque

def solve(nums, pairs):
   N = len(nums)
   P = len(pairs)
   v = [[] for i in range(N)]
   visited = set()
 
   for i in range(P):
      v[pairs[i][0]].append(pairs[i][1])
      v[pairs[i][1]].append(pairs[i][0])
 
   for i in range(N):
      if i not in visited:
         que = deque()
         arr_first = []
         arr_second = []
 
         visited.add(i)
         que.append(i)
 
         while len(que) > 0:
           u = que.popleft()
           arr_first.append(u)
           arr_second.append(nums[u])
 
           for s in v[u]:
               if s not in visited:
                 visited.add(s)
                 que.append(s)
 
         arr_first = sorted(arr_first)
         arr_second = sorted(arr_second)
         
         if arr_first != arr_second:
           return False
   return True
 
nums = [6,1,7,3,0,5,4,2]
pairs = [(0,4),(6,0),(2,7)]
print(solve(nums, pairs))

입력

[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]

출력

True