首页 > 代码库 > Leetcode: Pow(x, n)
Leetcode: Pow(x, n)
Implement pow(x, n).
Analysis:
The most basic idea, x multiply itself n time and return. However, this strait forward approach got time excessed. O(n).
Note that O(logn)< O(n)<O(n^2)<O(2^n). Therefore, we should consider about recursive approach, and divide n by 2 for each recursive call.
1 public class Solution { 2 public double pow(double x, int n) { 3 if (n < 0) { 4 return 1/helper(x, -n); 5 } 6 else return helper(x, n); 7 } 8 9 public double helper(double x, int n) {10 if (n == 0) return 1;11 double half = helper(x, n/2);12 if (n%2 == 0) {13 return half*half;14 }15 else return half*half*x;16 }17 }
参考网上的想法，把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。因为是对n进行二分，算法复杂度和上面方法一样，也是O(logn)。
Leetcode: Pow(x, n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。