LeetCode--Pow(x, n)

发布时间:2017-3-8 8:47:14编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode--Pow(x, n) ",主要涉及到LeetCode--Pow(x, n) 方面的内容,对于LeetCode--Pow(x, n) 感兴趣的同学可以参考一下。

Question

Implement pow(x, n).

解题思路

问题如此简单,第一反应求指数也就是求多个数的乘积,那么直接for循环走起,结果一提交发现超时了。

那么我们就来分析一下,如果用以上方法,那么时间复杂度为O(n), O(n)都超时了,说明时间复杂度还应该更低,多少呢?这个时候可以考虑log(n)了,什么样的算法可以达到log(n)呢?

那就是分治算法!if (n%2 == 0), x^n = x(n/2) * x(n/2); if (n%2 != 0), x^n = x(n/2) * x * x(n/2);

实现代码

#include <iostream>using namespace std;class Solution {public:    double power(double x, int n){        if(n==0)            return 1;        double v = power(x,n/2);        if(n%2 == 0)            return v *v;        else            return v* v* x;    }    double pow(double x, int n) {        if(n<0)            return 1.0 / power(x,-n);        else            return power(x,n);    }};int main() {    Solution* solution = new Solution();    cout << solution->pow(2, 4) << endl;    return 0;


上一篇:242. Valid Anagram
下一篇:RxJava系列6(从微观角度解读RxJava源码)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款