leetcode 50. Pow ( x, n )

题目描述:

实现 pow(x, n) ,即计算 x 的 n 次幂函数。

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

思路:

针对n=0, n>0 , n<0 三种情况,分支循环来一套:

double myPow(double x, int n) {
        if(n==0) return 1;
        double ans=x;
        if(n>0)
            while(--n)
                ans*=x;
        else
            ans=1/myPow(x,0-n);
        return ans;
    }

虽然时间复杂度是 O(n) ,但还是超出了时间限制...

换用分治法来做:

double myPow(double x, int n) {
        //先考虑特殊情况和递归出口
        if(n==0) return 1;
        if(x==1 || n==1) return x;
        double ans=0;
        if(n>0)
        {
            //分治
            double temp=myPow(x,n/2);
            ans=temp*temp;
            if(n%2==1)
                ans=ans*x;
        }
        else
            ans=1/myPow(x,0-n);
        return ans;
    }

结果执行出错了!出错输入是:x=2, n= -2147483648。

这个我猜测是n溢出了!由于32位有符号整数的范围是:-2147483648 ~ 2147483647,我把-2147483648从负数转化为正数时,它不能正确表示。改一下代码:

double myPow(double x, int n) {
        //先考虑特殊情况和递归出口
        if(n==0) return 1;
        if(x==1 || n==1) return x;
        double ans=0;
        if(n>0)
        {
            //分治
            double temp=myPow(x,n/2);
            ans=temp*temp;
            if(n%2==1)
                ans=ans*x;
        }
        else
        {
            //特殊情况 n=INT_MIN,把它+1防止后续计算 0-n 溢出。
            if(n==INT_MIN)
                ans= myPow(x,n+1)*1/x;
            else ans=1/myPow(x,0-n);
        }
        return ans;
    }

成功通过~

每次递归,问题规模减半,所以时间复杂度是O( log n );每次递归要用 double temp 保留中间值,空间复杂度O( log n )。

测试运行时间 20 ms。

看了一下最快的代码,他把n=2也作为递归出口直接计算了。这是个好思路,可以省去将近一半的递归开销时间。

受到他的启发,我有一个新的想法:能不能把所有的递归开销时间都节省下来?也就是把递归改成循环。

事实上是可以的!利用上面递归的递推式:当n是偶数,f(x, n) = f(x, n/2) ^ 2,当n是奇数,f(x,n) = f( x, n/2 ) ^ 2 * x,这里的/是整除。...这个反向的思路比较复杂,很难描述。

double myPow(double x, int n) {
        if(n==0) return 1;
        double ans=1;
        if(n>0)
        {
           double temp=x;
            //分n是奇数和偶数
            while(n)
            {
                if(n%2==1)
                    ans*=temp;
                temp=temp*temp;
                n=n/2;
            }
        }
        else
            ans=1/x/myPow(x,-(n+1));
        return ans;
    }

这个算法时间复杂度也是O( log n ),而空间复杂度是 O(1)。另外它省掉了递归的函数调用时间。

;