检查数组是否只能在 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