Skip to content

50. powx n

难度:Medium

刷题内容

原题连接

  • https://leetcode.com/problems/powx-n/

内容描述

mplement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [?2^31, 2^31 ? 1]

思路1 **- 时间复杂度: O(lgN)*- 空间复杂度: O(1)***

求一个数的n次方是我们经常用的函数,一般刚开始可能会用暴力的方法去求,做了n次循环,但由于这里的n非常大,单纯的暴力会TLE,这里可以用分治的思想,比如2*2*2*2,我们前面已经计算过2*2了,那么后面就不用再计算依次,就相当于2*2*(2*2),这样时间复杂度就变成了lgN,接下来只要主要幂次是负数的情况即可

class Solution {
public:
    double Pow(double x, long long n)
    {
        if(!n)
            return 1;
        if(n == 1)
            return x;
        double temp = Pow(x,(n)/ 2);
         double ret;
        if(n&1)
            ret = temp * temp * x;
        else
            ret = temp * temp;
        return ret;
    }
    double myPow(double x, int n) {
        long long k = n;
        if(n < 0)
            x = 1 / x;
        return Pow(x,n);
        }
};


回到顶部