16. 数值的整数次方

题目链接

Leetcode

题目描述

给定一个 double 类型的浮点数 x 和 int 类型的整数 n，求 x 的 n 次方。

解题思路

最直观的解法是将 x 重复乘 n 次，x*x*x...*x，那么时间复杂度为 O(N)。因为乘法是可交换的，所以可以将上述操作拆开成两半 (x*x..*x)* (x*x..*x)，两半的计算是一样的，因此只需要计算一次。而且对于新拆开的计算，又可以继续拆开。这就是分治思想，将原问题的规模拆成多个规模较小的子问题，最后子问题的解合并起来。

本题中子问题是 x^n/2，在将子问题合并时将子问题的解与自身相乘即可。但如果 n 不为偶数，那么拆成两半还会剩下一个 x，在将子问题合并时还需要多乘一个 x。

因为 x^n/2 可以通过递归求解，并且每次递归 n 都减小一半，因此整个算法的时间复杂度为 O(logN)。

n 为负数时，先把 x 换成 1/x，再求 x 的 -n 次方。需要注意的是，n 为 Integer.MIN_VALUE 时 -n 会溢出，因此先转成 long 再取反。

public double myPow(double x, int n) {
    long b = n;
    if (b < 0) {
        x = 1 / x;
        b = -b;
    }
    return pow(x, b);
}

private double pow(double x, long n) {
    if (n == 0) return 1;
    double res = pow(x, n / 2);
    res = res * res;
    if (n % 2 != 0) res *= x;
    return res;
}