Oliver's Blog

剑指Offer 面试题11：数值的整数次方

  • Jun 01, 2012

数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

解题思路

解法一

先处理base为0的情况。0的0次方无意义，题目已排除了这种情况。0的负数次方无意义，这里返回结果为0。0的正数次方结果也为0。然后通过乘法计算乘方，最后通过指数是否为负数确定是否需要求倒数。

解法二

利用以下公式，将时间复杂度降至O(log n)

\[a^n = \begin{cases} a^{\cfrac {n}{2}} \cdot a^{\cfrac {n}{2}} &(n为偶数)\\[3ex] a^{\cfrac {n - 1}{2}} \cdot a^{\cfrac {n - 1}{2}} \cdot a &(n为奇数 ) \end{cases}\]

代码

解法一

public class Solution {
    public double Power(double base, int exponent) {
        if(base == 0) {
            return 0;
        }
        int exponentAbs = Math.abs(exponent);
        double result = 1;
        for(int i = 0; i < exponentAbs; i++) {
            result *= base;
        }
        if(exponent >= 0) {
            return result;
        } else {
            return 1 / result;
        }
  }
}

解法二

public class Solution {
    public double Power(double base, int exponent) {
        if(base == 0) {
            return 0;
        }
        if(exponent == 0) {
            return 1;
        }
        if(exponent == 1) {
            return base;
        }
        if(exponent == -1) {
            return 1 / base;
        }
        double result;
        if(exponent % 2 == 0) {
            double halfPower = Power(base, exponent / 2);
            result = halfPower * halfPower;
        } else {
            double halfPower = Power(base, (exponent - 1) / 2);
            result = halfPower * halfPower;
            result *= base;
        }
        return result;
  }
}
Search