置换操作还原原数组次数算法问题：最优解逻辑错误排查

背景 #

某次求职编码测评中，我先用C++实现了解法（当时不允许用Python），之后用Python复现了相同逻辑并整理了问题描述。暴力解法通过15个测试用例中的6个，其余因超时未通过；最优解法通过8个，剩余隐藏测试用例（输出值极大）未通过。已排除LCM计算错误和整数溢出问题，怀疑环检测逻辑存在问题。

问题描述 #

要求返回将数组还原为原始状态所需的最少置换操作次数（至少执行1次操作）。
置换操作定义为：
tmp[i] = arr[p[i]] 对所有i成立，之后将arr替换为tmp。
其中p是长度为n的非空数组，元素为0到n-1的不重复值；arr是任意长度为n的数组。

暴力解法 #

暴力解法通过模拟置换过程实现，时间复杂度O(n²)，最坏情况下循环长度为n：

# O(n^2) since max cycle is at worst n long
def brute_force_sol(p):
    n = len(p)
    arr = [i for i in range(n)]
    num = 0
    while True:
        tmp = [0] * n
        for i in range(n):
            tmp[i] = arr[p[i]]
        arr = tmp
        num += 1
        if arr == [i for i in range(n)]:
            break
    return num

最优解法思路与实现 #

核心思路 #

观察到0到n-1的元素构成有向图的环，数组还原的最少操作次数等于所有环长度的最小公倍数（LCM）。例如：

• p = [1,4,3,2,0]，环为0→1→4→0（长度3）、2→3→2（长度2），LCM(2,3)=6
• p = [0,1]，环为0→0（长度1）、1→1（长度1），LCM(1,1)=1

实现代码（时间复杂度O(n)） #

# idea:
# observe that since 0 - (n - 1) are present, with each being a directed edge
# there form cycles that may sync up occassionally. we want to know when
# all the cycles sync up since that is the number of ops to get back to orig
# OR we want the LCM of the length of all the cycles present in the graph

# example:
# p = [1, 4, 3, 2, 0]
# cycle one: 0 -> 1 -> 4 -> 0 (len 3)
# cycle two: 2 -> 3 -> 2 (len 2)
# LCM(2, 3) = 6

# p = [0, 1]
# cycle one: 0 -> 0
# cycle two: 1 -> 1
# LCM(1, 1) = 1

# O(n)
def optimal_sol(p):
    n = len(p)
    a = set()
    cycles = []
    for i in range(n):
        if i in a:
            continue
        else:
            # track the cycle len
            j = i
            start = j
            cycleLen = 0
            
            while True:
                a.add(j)
                j = p[j]
                cycleLen += 1
                if start == j:
                    break
            cycles.append(cycleLen)

    from math import lcm
    return lcm(*cycles)

错误排查与修复建议 #

经过对环检测逻辑的验证，核心遍历逻辑无明显错误，问题大概率出在math.lcm的实现兼容性上。Python 3.9新增的math.lcm在处理极大数值时可能存在未知的环境或实现问题，建议替换为手动实现的LCM计算函数：

from math import gcd

def compute_lcm(numbers):
    lcm = 1
    for num in numbers:
        lcm = lcm * num // gcd(lcm, num)
    return lcm

# 修改optimal_sol中的返回语句
def optimal_sol(p):
    n = len(p)
    a = set()
    cycles = []
    for i in range(n):
        if i in a:
            continue
        else:
            j = i
            start = j
            cycleLen = 0
            
            while True:
                a.add(j)
                j = p[j]
                cycleLen += 1
                if start == j:
                    break
            cycles.append(cycleLen)

    return compute_lcm(cycles)

手动实现的LCM通过迭代计算两两数值的LCM，依赖更稳定的gcd函数，能避免内置lcm在处理超大数时的潜在问题。

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