检查数组是否只能在 Python 中使用给定索引之间的交换进行排序
假设我们有一个名为nums的数组，其唯一值范围为[0,n–1]。此数组未排序。我们还有另一个对的数组，其中每对包含可以交换数组元素的索引。我们可以多次交换。我们必须检查是否可以使用这些交换按排序顺序排列数组。
所以，如果输入像nums=[6,1,7,3,0,5,4,2]对=[(0,4),(6,0),(2,7)]，那么输出将是True，因为我们可以交换索引(2,7)数组将是[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:=nums的大小，P:=对数组中的对数
v:=包含N个子列表的列表
访问:=一个新集合
对于0到P范围内的i，执行
将pairs[i]的第二个索引插入v[pairs[i]的第一个索引]
将pairs[i]的第一个索引插入v[pairs[i]的第二个索引]
对于0到N范围内的i，请执行
que:=双端队列
arr_first:=一个新列表
arr_second:=一个新列表
将我标记为已访问
在que的末尾插入i
当que不为空时，做
arr_first:=排序列表arr_first
arr_second:=排序列表arr_second
如果arr_first与arr_second不同，则
如果未访问s，则
将s标记为已访问
在que末尾插入s
u:=que的前部元素并删除que的前部元素
在arr_first的末尾插入u
在arr_second末尾插入nums[u]
对于v[u]中的每个s，做
返回错误
如果我没有被访问，那么
返回真
让我们看看以下实现以获得更好的理解-
示例代码
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