时间戳

首页 > 解决方案 > 对一串 X、Y 和 Z 字符进行排序的最小交换次数

python - 对一串 X、Y 和 Z 字符进行排序的最小交换次数

问题描述

我需要找到以随机顺序和数量（不仅是相邻的）对只有字母 X、Y 和 Z 的字符串进行排序所需的最小交换量。任何两个字符都可以交换。

例如，字符串 ZYXZYX 将在 3 个交换中排序：ZYXZYX -> XYXZYZ -> XXYZYZ -> XXYYZZ ZZXXYY - 在 4 个交换中，XXXX - 在 0 个交换中。

到目前为止，我有这个解决方案，但是排序并没有以最佳方式对字符进行排序，因此结果并不总是最小的交换量。此外，解决方案应该是 O(nlogn)。

def solve(s):
  n = len(s)
  newS = [*enumerate(s)] 
  sortedS = sorted(newS, key = lambda item:item[1])

  counter = 0
  vis = {v:False for v in range(n)} 
  print(newS)
  print(sortedS)

  for i in range(n):
    if vis[i] or sortedS[i][0] == i: 
      continue
    cycle_size = 0
    j = i 

    while not vis[j]: 
      vis[j] = True 
      j = sortedS[j][0] 
      cycle_size += 1
    
    if cycle_size > 0: 
      counter += (cycle_size - 1) 

  return counter

标签： pythonalgorithmsorting

解决方案

首先执行 O(n) 遍历数组并计算 X、Y 和 Z。根据计数，我们可以在数组中定义三个区域：Rx、Ry 和 Rz。Rx 表示数组中 X 应该去的索引范围。Ry 和 Rz 也是如此。

那么正好有 6 个排列需要考虑：

Rx  Ry  Rz
X   Y   Z     no swaps needed
X   Z   Y     1 swap: YZ
Y   X   Z     1 swap: XY
Y   Z   X     2 swaps: XZ and XY
Z   X   Y     2 swaps: XZ and YZ
Z   Y   X     1 swap: XZ

因此，您只需要再进行五次 O(n) 次传递即可修复每个可能的排列。从需要 1 次交换的情况开始。然后修复 2 个交换案例，如果有的话。

例如，查找和修复 XZY 排列的伪代码是：

y = Ry.start
z = Rz.start
while y <= Ry.end && z <= Rz.end
   if array[y] == 'Z' && array[z] == 'Y'
      array[y] <--> array[z]
      swapCount++
   if array[y] != 'Z'
      y++
   if array[z] != 'Y'
      z++

每个排列的运行时间为 O(n)，总运行时间为 O(n)。

正确性的正式证明留给读者作为练习。我只注意到 XZY、YXZ 和 ZYX 案例以一次交换为代价修复了两个元素（效率 2），而 YZX 和 ZXY 案例以两次互换为代价修复了三个元素（效率 1.5）。因此，首先找到并修复有效案例（并仅在需要时执行低效案例）应该给出最佳答案。

推荐阅读