檢查陣列是否僅使用給定索引之間的交換在 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 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告

© . All rights reserved.