检查数组是否仅使用给定索引之间的交换在 Python 中进行排序

假设我们有一个名为 nums 的数组，其中包含来自范围 [0，n – 1] 的唯一值。此数组未排序。我们还有另一个配对数组，其中每个配对包含数组元素可以交换的索引。我们可以交换多次。我们必须检查我们是否可以使用这些交换将数组排列成排序顺序。

因此，如果输入类似于 nums = [6,1,7,3,0,5,4,2] pairs = [(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 := pairs 数组中的配对数
  • v := 一个包含 N 个子列表的列表
  • visited := 一个新的集合
  • 对于 i 从 0 到 P，执行以下操作：
    • 将 pairs[i] 的第二个索引插入 v[pairs[i] 的第一个索引] 中
    • 将 pairs[i] 的第一个索引插入 v[pairs[i] 的第二个索引] 中
  • 对于 i 从 0 到 N，执行以下操作：
    • 如果 i 未被访问，则：
      • que := 一个双端队列
      • arr_first := 一个新的列表
      • arr_second := 一个新的列表
      • 将 i 标记为已访问
      • 将 i 插入 que 的末尾
      • 当 que 不为空时，执行以下操作：
        • u := que 的第一个元素，并删除 que 的第一个元素
        • 将 u 插入 arr_first 的末尾
        • 将 nums[u] 插入 arr_second 的末尾
        • 对于 v[u] 中的每个 s，执行以下操作：
          • 如果 s 未被访问，则：
            • 将 s 标记为已访问
            • 将 s 插入 que 的末尾
      • arr_first := 对列表 arr_first 进行排序
      • arr_second := 对列表 arr_second 进行排序
      • 如果 arr_first 与 arr_second 不相同，则：
        • 返回 False
  • 返回 True

让我们看看以下实现以获得更好的理解：

示例代码

实时演示

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

更新于: 2021年1月15日

105 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告