剑指offer系列——数值的整数次方

题目描述

实现函数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/2^2 = 1/4 = 0.25

说明：

• -100.0< x <100.0
• n是32位有符号整数，其数值范围是[-2^31，231 -1]。

算法思路(二分法)

• 当n是偶数时，x^n = (x²⁾(n/2)
• 当n是奇数时，x^n = x(x²⁾(n/2)，相比偶数多出了一项x
• 

代码

package leetcode;

/**
 * @author god-jiang
 * @date 2020/3/10  19:41
 */
public class Power {
    public double myPow(double x, int n) {
        //避免当n为最大值时，进行n=-n时数据越界出错
        long exponent = n;
        if (n < 0) {
            x = 1 / x;
            exponent = -exponent;
        }
        double res = 1.0;
        while (exponent != 0) {
            //奇数多出了一项x
            if ((exponent & 1) == 1) {
                res = res * x;
            }
            //二分操作
            x = x * x;
            exponent = exponent >> 1;
        }
        return res;
    }
}

通过截图

复杂度分析

• 时间复杂度：O(logN)。跟二分操作的时间复杂度一样
• 空间复杂度：O(1)。没有引入额外的变量

ps：参考leetcode大佬Krahets的解答。