LeetCode 50. Pow(x, n)

xiaoxiao2021-02-28  62

快速幂

本题要求x的n次方,n很大,所以O(n)的解法肯定不行,只能考虑O(logn)复杂度的解法。我们可以想到,若 n n 为偶数,xn=(x2)n/2xn=(x2)n/2,若 n n 为奇数,则xn=xx(n1)/2xn=x·x(n−1)/2,由此可以想到由递归方式来解决。代码: class Solution { public: double myPow(double x, int n) { if (n == 0) return 1; else { long long t = (long long)n; if (n<0) t = -(long long)n; if (t % 2 == 0) { x = myPow(x*x, t / 2); } else { x = myPow(x, t - 1)*x; } if (n<0) x = 1 / x; return x; } } };
转载请注明原文地址: https://www.6miu.com/read-2600196.html

最新回复(0)