剑指 Offer 16. 数值的整数次方

深藏阁楼爱情的钟 2022-12-17 08:51 78阅读 0赞

# 题目 #

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

> 输入: 2.00000, 10  
> 输出: 1024.00000

示例 2:

> 输入: 2.10000, 3  
> 输出: 9.26100

示例 3:

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

说明:

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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof][https_leetcode-cn.com_problems_shu-zhi-de-zheng-shu-ci-fang-lcof]

# 解题思路 #

直接相乘,时间复杂度为O(n)  
使用快速幂法,可以降低时间复杂度为O( l o g 2 n log\_2\{n\} log2n)

*  底数为0时,特殊处理
 *  指数小于0时,需要进行转换,这个时候需要注意int类型取相反数溢出问题,所以使用long类型接收
 *  初始化结果result = 1.0
 *  使用快速幂法,当指数不为0时,开始迭代
    
     *  若指数为奇数,则抽取出一个底数乘入结果
     *  底数取平方,即自身相乘,此时指数相当于拆分成n = 2 \* (n >> 1)
     *  指数右移一位,相当于除2
     *  当指数为0时退出循环,否则继续循环
 *  返回result

# 代码 #

class Solution { 
        public double myPow(double x, int n) { 
            // 特殊情况
            if (x == 0) { 
                return 0;
            }
    
            // int类型的取值范围为[−2^31, 2^31 − 1]
            // 指数小于0取相反值的时候可能出现越界,所以使用long类型接收
            long a = n;
            // 如果指数为负数,则进行转换
            if (a < 0) { 
                x = 1 / x;
                a = -a;
            }
    
            double result = 1.0;
            // 当指数不为0时,迭代
            while (a > 0) { 
                // (a & 1) == 1说明最低位为1,则说明指数为奇数,此时抽出一个底数乘入乘积
                if ((a & 1) == 1) { 
                    result *= x;
                }
                // 底数取平方,即自身相乘
                x *= x;
                // 指数右移一位,即除以2
                a >>>= 1;
            }
            return result;
        }
    }

# 复杂度 #

*  时间复杂度:O( l o g 2 n log\_2\{n\} log2n)
 *  空间复杂度:O(1),a,result等变量占用常数大小额外空间

[https_leetcode-cn.com_problems_shu-zhi-de-zheng-shu-ci-fang-lcof]: https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof