【算法题解】37. Pow(x, n)

Myth丶恋晨 2024-03-16 16:08 41阅读 0赞

> 这是一道 **中等难度** 的题  
> https://leetcode.cn/problems/powx-n/

### 题目 ###

实现  p o w ( x , n ) pow(x,n) pow(x,n) ，即计算 `x` 的整数 `n` 次幂函数（即， x n x^n xn）。

**示例 1：**

输入：x = 2.00000, n = 10 
    输出：1024.00000

**示例 2：**

输入：x = 2.10000, n = 3 
    输出：9.26100

**示例 3：**

输入：x = 2.00000, n = -2 
    输出：0.25000 解释：2^{-2} = 1/2^2 = 1/4 = 0.25

**提示：**

*   − 100.0 < x < 100.0 -100.0 < x < 100.0 −100.0<x<100.0
 *   − 2 31 < = n < = 2 31 − 1 -2^\{31\} <= n <= 2^\{31\}-1 −231<=n<=231−1
 *  `n` 是一个整数
 *  要么 `x` 不为零，要么  n > 0 n > 0 n>0 。
 *   − 1 0 4 < = x n < = 1 0 4 -10^4 <= xn <= 10^4 −104<=xn<=104

--------------------

### 题解 ###

这道题的暴力解法就是一个简单的 `for` 循环，循环 `n` 次，时间复杂度为  O ( N ) O(N) O(N)。

double ans = 1;
    for(int i = 0; i < n; i++){
        
        ans *= x;
    }

暴力解法当然不是最优解，不做考虑。

本题可以使用分治的思路去递归，我们知道  x n = x n / 2 ∗ x n / 2 x^n = x^\{n/2\} \* x^\{n/2\} xn=xn/2∗xn/2 。

所以要求得  x n x^n xn ，我们只需要知道  x n / 2 x^\{n/2\} xn/2 即可。

同样的，要求得  x n / 2 x^\{n/2\} xn/2 ，我们只需要知道  x n / 4 x^\{n/4\} xn/4 即可。

以此类推，每次只需要求得其中的一半，就可以推导出结果，最终时间复杂度为 O ( l o g N ) O(logN) O(logN)。

**需要注意的点：**

1.  **边界条件 n == 0**时：直接返回 `1`。
2.  **n < 0**时：转换为  x n = ( 1 / x ) − n x^n = (1 / x)^\{-n\} xn=(1/x)−n。这里还**需要特别注意的一点是当  n = − 2 31 n = -2^\{31\} n=−231 时， − n -n −n 会越界**，所以需要特殊处理，我们让  x n = x n + 1 / x x^n = x^\{n + 1\} / x xn=xn\+1/x，这样再使用 `n < 0` 这个条件去处理，就不会越界了。
3.  **n 为奇数**的时候：如  n = 5 n = 5 n=5, 那么用上面的公式 x 5 = x 5 / 2 ∗ x 5 / 2 x^5 = x^\{5/2\} \* x^\{5/2\} x5=x5/2∗x5/2 变为  x 2 ∗ x 2 = x 4 x^2 \* x^2 = x^4 x2∗x2=x4。计算的结果就会少乘了一个 `x`， 所以最后需要补乘一个 `x` 。

##### Java 代码实现 #####

class Solution {
        
        public double myPow(double x, int n) {
        
    
            // 边界条件
            if(n == 0){
        
                return 1;
            }
    
            // 如果 n 是负数
            if(n < 0){
        
                if(n == -(1 << 31)){
        
                    return myPow(x, n + 1) / x;
                }
                return myPow(1 / x, -n);
            }
             
            double temp =  myPow(x, n / 2);
    
            double ans = temp * temp;
            // 如果 n 是奇数
            if(n % 2 == 1){
        
                ans = ans * x;
            }
    
            return ans;
        }
    }

##### Go 代码实现 #####

func myPow(x float64, n int) float64 {
        
        // 边界条件
        if n == 0 {
        
            return 1
        }
    
        if n < 0 {
        
            if n == -(1 << 31) {
        
                return myPow(x, n + 1) / x
            }
            return myPow(1 / x, -n)
        }
    
        temp := myPow(x, n / 2)
    
        ans := temp * temp
        if n % 2 == 1 {
        
            ans = ans * x
        }
    
        return ans
    
    }

##### 复杂度分析 #####

**时间复杂度**： O ( l o g ⁡ N ) O(log⁡ N) O(log⁡N)。

**空间复杂度：** O ( l o g ⁡ N ) O(log⁡ N) O(log⁡N)。