LeetCode 50. Pow(x, n)

2024-01-07 20:45:33

Pow(x, n)

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

方法一、快速幂 + 递归

比较容易联想到递归,x的n次方可递归表示为x乘以x的n-1次方。

快速幂的使用:举个🌰,x的20次方,我们为了提高效率,可以用x^10 * x^10表示,类似二分法的思想。
注意:

  • n为负数时取正数结果的倒数即可。
  • 奇数时由于除2,会丢失一个x,因此需要补上。

复杂度分析:
时间复杂度:O(logn)
空间复杂度:O(n)

Swift

func myPow(_ x: Double, _ n: Int) -> Double {
    let N = n
    let res = N > 0 ? quiMul(x, N) : 1/quiMul(x, -N)
    return res
}

func quiMul(_ x:Double, _ n:Int) -> Double {
    if n == 0 {
        return 1
    }
    
    let y = quiMul(x, n/2)//对半劈开,x^4 = x^2 * x^2
    return n % 2 == 0 ? y * y : y*y*x
}

OC

-(double)myPow:(double)x n:(NSInteger)n {
    NSInteger N = n;
    
    return N > 0 ? [self quickMul:x n:N] : 1/[self quickMul:x n:-N];
}

-(double)quickMul:(double)x n:(NSInteger)n {
    if (n == 0) {
        return 1;
    }
    
    double y = [self quickMul:x n:n/2];
    return n % 2 == 0 ?  y*y : x*y*y;
}

方法二、快速幂+迭代法

递归占用了栈空间,那么能否实现一种空间复杂度为1的算法呢?
技巧性较强,需要找到规律。
发现规律
这样以来,我们从 x开始不断地进行平方,得到 x2,x4,x8,x16,?, 如果 n的第 k 个(从右往左,从 0 开始计数)二进制位为 1,那么我们就将对应的贡献计入答案。

复杂度分析:
时间复杂度:O(logn)
空间复杂度:O(1)

Swift

func myPow(_ x: Double, _ n: Int) -> Double {
    let N = n
    let res = N > 0 ? quiMul(x, N) : 1/quiMul(x, -N)
    return res
}

//递归法清晰,但是占用了栈空间,因此,我们使用迭代实现
func quiMul(_ x:Double, _ n:Int) -> Double {
    
    var N = n
    var ans:Double = 1.0;
    
    var contribute = x
    while N > 0 {
        if N % 2 == 1 {
            ans *= contribute
        }
        
        //将贡献不断地平方
        contribute *= contribute
        
        N /= 2
    }
    
    return ans
}

OC

-(double)myPow:(double)x n:(NSInteger)n {
    NSInteger N = n;
    
    return N > 0 ? [self quickMul:x n:N] : 1/[self quickMul:x n:-N];
}

-(double)quickMul:(double)x n:(NSInteger)n {
    double x_contribute = x;
    double ans = 1.0;
    while (n > 0) {
        if (n % 2 == 1) {
            ans *= x_contribute;
        }
        
        x_contribute *= x_contribute;
        
        n /= 2;
    }
    return ans;
}

文章来源:https://blog.csdn.net/zzl819954692/article/details/135392433
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。