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

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

难度：$middle$

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^{n}）。不得使用库函数，同时不需要考虑大数问题。

示例 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/22 = 1/4 = 0.25

提示：

• $-100.0<x<100.0$
• $-2^{31}<=n<=2^{31}-1$
• $-10^4<=x^n<=10^4$

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

算法

(快速幂算法)

快速幂实际上是二分思想的一种应用。

• 当 $n$ 是 奇数 的时候 $a^n=a^{n/2}\ast a^{n/2}$
• 当 $n$ 是 偶数 的时候 $a^n=a^{n-1/2}\ast a^{n-1/2}\ast a$

复杂度分析

• 时间复杂度：$O(lo{g}_{2}n)$

• 空间复杂度 : $O(1)$

C++ 代码

class Solution {
public:

    double quickmul(double x, long long m) {
        if (m == 0) return 1.0;

        double result = myPow(x, m >> 1);
        result *= result;
        if (m & 1 == 1) result *= x;
        return result;
    }

    double myPow(double x, int n) {
        long long m = n;// 不能直接用n做计算。
        if (n >= 0) return quickmul(x, m);

        return 1.0 / quickmul(x, -m);
    }
};