Leetcode Pow(x,n)递归优化实现出错，求排查结果不符问题

我在实现Leetcode的Pow(x,n)（计算x的n次幂）功能时，尝试用(xⁿ)^ᵐ = x^(n*m)的原理优化时间复杂度，但运行结果与预期不符。正确答案应为1.13074，而我得到的是1.06336，恳请帮忙排查代码缺陷。

实现代码 #

function getMiddleFactors(n: number): number[] {
    const factors = [];
    for(let i = 1; i <= n; i=i+1) {
        if(n%i===0) {
            factors.push(i);
        }
    }

    return [factors[Math.floor(factors.length/2) - 1], factors[Math.floor(factors.length/2)]]
}

function myPow(x: number, n: number): number {
    let answer = 1;
    const negative = n < 0;

    if(negative) {
        n = -n;
    }

    if(n < 20) {
        for(let i = 0; i < n; i=i+1) {
            answer = answer * x;
        }
    } else {
        const factors = getMiddleFactors(n);
        console.log(`Got the factors: ${factors}`)
       
        const inner = myPow(x, factors[0]);
        console.log(`Got the inner number ${x}^${factors[0]}: ${inner}`);

        answer = myPow(inner,factors[1]);
        console.log(`Got the answer for ${x}^${n} (${inner}^${factors[1]}): ${answer}`);
    }
    
    if(negative) {
        answer = 1/answer;
    }

    return answer
};

运行输出 #

Got the factors: 16,32
Got the inner number 1.00012^16: 1.0019217289680562
Got the factors: 4,8
Got the inner number 1.0019217289680562^4: 1.0077091025273281
Got the answer for 1.0019217289680562^32 (1.0077091025273281^8): 1.0633627729389192
Got the answer for 1.00012^1024 (1.0019217289680562^32): 1.0633627729389192

问题分析 #

核心错误出在getMiddleFactors函数：

• 该函数返回的两个因子乘积不等于输入的n。以测试用例中的n=1024为例，它的因子列表是[1,2,4,8,16,32,64,128,256,512,1024]，函数取的是第4位（16）和第5位（32），但16*32=512≠1024，这导致你实际计算的是x^512而非x^1024，最终结果自然偏小。
• 你的逻辑依赖a*b = n才能保证(x^a)^b = x^n，但当前函数的取值逻辑完全不满足这个前提。

修复方案 #

方案1：修正因子获取逻辑 #

修改getMiddleFactors，确保返回的两个因子乘积等于n。比如取最接近平方根的一对因子：

function getMiddleFactors(n: number): number[] {
    let a = 1;
    // 找到最大的a <= sqrt(n)且能整除n
    for (let i = Math.floor(Math.sqrt(n)); i >= 1; i--) {
        if (n % i === 0) {
            a = i;
            break;
        }
    }
    return [a, n / a];
}

方案2：改用标准快速幂实现（更高效） #

快速幂的核心是分治思想，时间复杂度O(logn)，且逻辑更简洁不易出错：

function myPow(x: number, n: number): number {
    if (n === 0) return 1;
    const negative = n < 0;
    n = Math.abs(n);
    
    // 递归分治
    const half = myPow(x, Math.floor(n / 2));
    const result = n % 2 === 0 ? half * half : half * half * x;
    
    return negative ? 1 / result : result;
}

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