力扣刷题——二分查找实现pow幂函数

1、先来个例题:
力扣刷题——二分查找实现pow幂函数

取值范围:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1

举个例子:
输入:x=2 n=10
输出:1024
输入:x=2 n=-2
输出:0.25 (因为1/4=0.25)

给出方法

public double myPow(double x, int n) {
}

2、分析

思路一:

蛮力法

根据幂函数定义直接求解,即2的10次方=2 * 2 *… * 2(10个2相乘)

代码实现:略



优点:思路清晰,简单直接易懂。
缺点:时间复杂度O(n),当n足够大时,程序运行超时。

按照目前思路,没有太多优化提升的余地。




思路二:
减治法-二分查找

减治法的基本思路是,将当前实例的解与其较小实例解建立关系。

先看个例子:
力扣刷题——二分查找实现pow幂函数

当n>0时,
1)n是偶数,求解等价于(n/2)^2,比如上面的10/2=5。
2)当n是奇数,等价于x * x^(n-1),
比如
力扣刷题——二分查找实现pow幂函数

当n<0时,
力扣刷题——二分查找实现pow幂函数

基本类似n>=0的情况。

当n=0时,直接返回1。

代码实现:

第一版

 public double myPow(double x, int n) {
         while(n>=1 || n<=-1){
            if(n % 2==0){
                n=n/2;

                if(n>0){
                    return myPow(x,n)*myPow(x,n);
                }else {
                    n=-n;
                    return 1/myPow(x,n)*myPow(x,n);
                }
            }else {
                if(n==1) return x;
                if(n==-1) return 1/x;
                if(n>0){
                    n--;
                    return x*myPow(x,n);
                }else {
                    n++;
                    n=-n;
                    return 1/(x*myPow(x,n));
                }

            }
        }
        return 1;
    }

运行后仍然超时,稍微修改一下。



第二版

将下面这行代码
return myPow(x,n)*myPow(x,n);
修改为:
 double y=myPow(x,n);
 return y*y;

力扣刷题——二分查找实现pow幂函数

Tips:
递归时,可使用变量,尽量减少递归的次数。否则容易出现栈溢出或超时等问题。

运行通过,缺点也很明显。代码有点冗长,分了三大种情况,可以继续抽象。




第三版

 public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

与之前的版本相比:
a. 更加充分的利用了递归的特性,不再需使用while。

b. 使用三目表达式
减少了冗余繁琐的if…else…
同样的,也增加的理解的难度。

c.更加抽象
结束递归的口径唯一,进行了更多的抽象。代码更加简洁。

3、小结

二分查找是减治法的一个具体实现算法,他将求解n与n/2联系起来,找到之间关联。然后利用这种关联,加上结束条件(比如n=1或者n=0时,有已知值)。

旨在降低时间复杂度,提高运行效率。相应的,代码可能不太好理解。

上一篇:JAVA操作MySQL数据库


下一篇:50. Pow(x, n)