leetcode:50.Pow(x, n)

叁歲伎倆 2022-01-28 09:11 204阅读 0赞

### 题目描述： ###

实现 `pow(x, n)`，即计算 x 的 n 次幂函数。

###### 示例1： ######

输入: 2.00000, 10
    输出: 1024.00000

###### 示例2： ######

输入: 2.10000, 3
    输出: 9.26100

###### 示例3： ######

输入: 2.00000, -2
    输出: 0.25000
    解释: 2^-2 = 1/2^2 = 1/4 = 0.25

###### 说明： ######

*  \-100.0 < x < 100.0
 *  n 是 32 位有符号整数，其数值范围是 \[ − 2 31 , 2 31 − 1 \] \{ \[−2^\{31\}, 2^\{31\} − 1\]\} \[−231,231−1\] 。

##### 题目难度：中等 #####

##### 分析： #####

如果直接调用API的话：`return Math.pow(x, n)`即可。  
计算 `x`的 `n`次幂函数也就是计算 `n`个 `x`相乘。但是如果直接用`for`循环计算的话，当 `n`特别大的时候就会超出时间限制，显然不能这么去计算。但是可以用`分治算法`的思想把时间复杂度从  O ( n ) O(n) O(n) 缩短到  O ( l o g 2 n ) O(log\_2n) O(log2n) 。简单点来说就是两两相乘，把 `n`个`x`分成两部分，比如`n`为`8`时，前`4`后`4`，那么就变成了 x 4 x^4 x4 \*  x 4 x^4 x4，此时只需要计算一个 x 4 x^4 x4的结果然后再和自身相乘即可，同理 x 4 x^4 x4也可以拆分成 x 2 x^2 x2 \*  x 2 x^2 x2 ，以此类推，即可大大缩短用时。这里其实有点类似`折半查找`。  
代码如下：

class Solution { 
        public double myPow(double x, int n) { 
        	// 判断n是正是负
            int pow = n > 0 ? 1 : -1;
            // 最终结果，定义成1在相乘时不影响结果
            double res = 1;
            // 循环相乘即可，这里利用n的奇偶性来判断
            while (n != 0) { 
                if (n % 2 != 0) { 
                    res *= x;
                }
                x *= x;
                n /= 2;
            }
            // 如果n是负数，这里要把前面的结果取倒数
            if (pow == -1) { 
                return 1 / res;
            }
            return res;
        }
    }

##### 总结： #####

时间复杂度为 O ( l o g 2 n ) O(log\_2n) O(log2n)，利用了分治的思想可以缩短用时。