首页 > 代码库 > leetcode. Pow(x, n)
leetcode. Pow(x, n)
Implement pow(x, n).
直接把x自乘n-1次很容易实现，时间复杂度O(n).
实际上，x^n = x^(n/2) * x^(n/2), 这样只需要求一次 x^(n/2)，再做一次乘操作即可，T(n) = T(n/2) + c, T(n) = lbn. (参见 CLRS 主定理)
同时要注意两个细节：
1、n可能为负数，需要取倒数，即 x^n = 1/(x^(-n)).
2、最小负数0x80000000直接转正数会溢出。
1 double powpositive(double x, int n) 2 { 3 double ret = 0; 4 if (n == 0) 5 return 1; 6 7 ret = powpositive(x, n >> 1); 8 if (n & 1) 9 return ret * ret * x;10 else11 return ret * ret;12 }13 14 double pow(double x, int n)15 {16 if (n >= 0)17 {18 return powpositive(x, n);19 }20 else21 {22 if (n == 0x80000000)23 return 1 / (powpositive(x, 0x7fffffff) * x);24 else25 return 1 / (powpositive(x, -n));26 27 }28 }
leetcode. Pow(x, n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。