抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

22 | 面试题:Pow(x,n)

50. Pow(x, n)

解法一:直接使用系统函数。

时间复杂度:O(1)

解法二:暴力,for 循环。

时间复杂度:O(N)

解法三:分治,整个分两边,考虑奇偶

偶数时:结果=X^n/2 * X^n/2

奇数时:结果=X^(n – 1)/2 * X^(n – 1)/2 * X,同时由于是取整,所以是:X^n/2 * X^n/2 * X

一直拆分下去,时间复杂度: O(logN)

这个更清楚,leetcode 题解:50. Pow(x, n) (快速幂,清晰图解)

递归版:

class Solution {
    fun myPow(x: Double, n: Int): Double {
        //终止条件
        if (n == 0) return 1.0
        if (n == 1) return x
        if (n == -1) return 1/x
        val half = myPow(x, n / 2)
        val rest = myPow(x, n % 2)
        return rest * half * half
    }
}

非递归版:注意这里转 Long 不是没有原因的,超出限制了。

上面题解中的一张图很适合这份代码:

在这份代码中,当 n 为奇数时,会先乘上一个 x,最后再存下结果,n 为偶数时,只会在最后存在结果。这部分代码解决了奇偶性条件问题,而且这代码位置摆放得也很妙。

if (times % 2 == 1L) res *= num
class Solution {
    fun myPow(x: Double, n: Int): Double {
        var times = n.toLong()

        if (x == 0.0) return x

        var num = x

        if (times < 0) {
            num = 1 / num
            times *= -1
        }
        var res = 1.0
        while (times > 0) {
            if (times % 2 == 1L){
                res *= num
            }
            num *= num
            times /= 2
        }
        return res
    }
}


0条评论

发表评论