检查数组是否只能在 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 dequedef 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
以上是 检查数组是否只能在 Python 中使用给定索引之间的交换进行排序 的全部内容， 来源链接： utcz.com/z/327627.html
