[Leetcode] Pow(x, n)

Pow(x, n) 题解

题目来源：https://leetcode.com/problems/powx-n/description/

---

Description

Implement pow(x, n).

Example

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Solution

class Solution {
public:
    double myPow(double x, int n) {
        if (x == 0)
            return 0;
        if (n == 0)
            return 1;
        double res;
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        if (n % 2 == 1) {
            res = x * myPow(x, n - 1);
        } else {
            double temp = myPow(x, n / 2);
            res = temp * temp;
        }
        return isinf(res) ? 0 : res;
    }
};

---

解题描述

这道题题意是实现一个pow函数。一开始的时候没有考虑优化，直接采用连乘，提交后总是超时。后来回想了一下，其实连乘做了很多重复操作，比如说从pow(x, n / 2)到pow(x, n)的计算过程中，连乘需要多计算n / 2次，但是很明显此时只需要一步平方操作即可。这样一来，时间复杂度是可以从O(n)降到O(log n)的。上面就是根据这个思想给出的递归解法。

同样的思想转换成迭代法如下：

class Solution {
public:
    double myPow(double x, int n) {
        if (x == 0)
            return 0;
        if (n == 0)
            return 1;
        double res = 1;
        if (n < 0) {
            x = 1 / x;
            n = -n;
            if (n < 0) { // 当n为最小负数时，取其相反数会导致溢出，使得n仍为最小负数
                if (x < 1 && x > -1)
                    return 0;
                else
                    return 1;
            }
        }
        while (n > 0) {
            if (n % 2 == 1) {
                res *= x;
            }
            x *= x;
            n /= 2;
        }
        return isinf(res) ? 0 : res;
    }
};