面试题：判断数组能否通过相邻三元素右旋操作转换为目标数组

嘿，这个问题我之前也琢磨过！先说说你递归思路的小局限，再给你一个更高效且通用的解法～

你的递归思路方向是对的，但有几个明显的问题：

• 效率问题：每次递归都要查找元素位置，还可能重复执行大量操作，时间复杂度会达到O(n²)甚至更糟，对于大数组来说不够高效。
• 边界情况处理不足：比如当目标元素在i+1的位置（和当前位置差1），或者数组末尾的元素需要调整时，递归可能会陷入重复操作，甚至无法处理。
• 重复元素场景不友好：如果数组中有重复元素，“找最靠左的目标元素”可能会导致错误的选择，无法完成正确转换。

我们可以用迭代+模拟移动的思路，从左到右逐个匹配元素，同时利用三相邻右旋的特性高效移动元素，还能处理重复元素和边界情况。

核心思路 #

三相邻右旋操作{a,b,c} → {c,a,b}有两个关键特性：

1. 可以将位置j的元素向左移动2位（对j-2, j-1, j执行右旋，元素从j到j-2）。
2. 可以将位置j的元素向右移动1位（对j-1, j, j+1执行右旋，元素从j到j+1）—— 这一步用来调整元素和目标位置的距离奇偶性。

基于这两个特性，我们可以逐个位置匹配，把目标元素“挪”到对应位置。

完整步骤 #

1. 基础校验 #

首先做几个快速判断，排除不可能的情况：

• 如果两个数组长度不同，直接返回false。
• 长度小于3时：
  • 长度为1：必须两个元素相等。
  • 长度为2：必须两个数组完全相同（因为没有3个相邻元素可操作）。
• 检查两个数组的元素频率是否完全一致（用哈希表统计每个元素出现次数），如果不一致，直接返回false。

2. 迭代匹配元素 #

将原数组转为可修改的列表，从左到右处理每个位置i：

• 如果当前元素已经和目标数组的B[i]匹配，直接跳过。
• 找到当前位置i之后第一个等于B[i]的元素位置j。
• 通过右旋操作将arr[j]移动到i的位置：
  • 如果j > i+1：每次对j-2, j-1, j执行右旋，把元素左移2位，直到j等于i或i+1。
  • 如果j == i+1：
    • 如果j+1 >= n（即已经到数组末尾），说明无法调整，返回false（这种情况对应置换奇偶性不匹配）。
    • 否则对j-1, j, j+1执行右旋，把元素右移1位（j变成j+1），然后继续左移2位的操作。

代码实现（Python） #

def can_transform(A, B):
    # 基础长度检查
    if len(A) != len(B):
        return False
    n = len(A)
    
    # 短数组特殊处理
    if n < 3:
        return A == B
    
    # 检查元素频率是否一致
    from collections import defaultdict
    count = defaultdict(int)
    for num in A:
        count[num] += 1
    for num in B:
        count[num] -= 1
        if count[num] < 0:
            return False
    for num in count:
        if count[num] != 0:
            return False
    
    # 转为列表方便修改
    arr = list(A)
    for i in range(n):
        if arr[i] == B[i]:
            continue
        
        # 找到后面第一个匹配的元素位置
        j = i
        while j < n and arr[j] != B[i]:
            j += 1
        if j == n:
            return False  # 理论上频率检查过不会出现
        
        # 把arr[j]移动到i的位置
        while j > i:
            if j > i + 1:
                # 左移2位：右旋j-2, j-1, j
                arr[j-2], arr[j-1], arr[j] = arr[j], arr[j-2], arr[j-1]
                j -= 2
            else:
                # j == i+1，先右移1位
                if j + 1 >= n:
                    return False  # 无法调整，返回失败
                arr[j-1], arr[j], arr[j+1] = arr[j+1], arr[j-1], arr[j]
                j += 1
    return True

复杂度分析 #

• 时间复杂度：O(n²)，最坏情况下每个元素都需要移动O(n)次，但比递归更高效（没有递归调用栈的开销，且操作更直接）。
• 空间复杂度：O(n)，用于存储数组副本和频率统计。

如果数组中所有元素都是唯一的，我们还可以通过逆序数奇偶性快速判断：

• 三相邻右旋是偶置换（可分解为两个对换），所以每次操作不会改变数组逆序数的奇偶性。
• 因此，当A和B的逆序数奇偶性不同时，直接返回false；否则返回true（前提是元素组成相同）。

这个方法的时间复杂度可以降到O(n log n)（用归并排序计算逆序数），比迭代法更高效，但只适用于元素唯一的场景。

内容的提问来源于stack exchange，提问作者Ankit Sharma