首页 > 代码库 > leetcode笔记:Pow(x, n)
leetcode笔记:Pow(x, n)
一. 题目描写叙述
Implement pow(x, n).
二. 题目分析
实现pow(x, n)。即求x
的n
次幂。
最easy想到的方法就是用递归直接求n
个x
的乘积,这里须要依据n
的值,推断结果是正数还是负数,这样的方法的时间复杂度为O(n)
。
更加快捷的方法是。使用分治法。对于x^n。有一下公式:
x^n = x^(n / 2) * x^(n / 2) * x^(n % 2)
使用这样的方法的时间复杂度为O(logn)
。
三. 演示样例代码
#include <iostream>
using namespace std;
class Solution {
public:
double pow(double x, int n)
{
if (n == 0)
return 1;
if (n > 0)
return power(x, n);
else
return 1 / power(x, -1 * n);
}
private:
double power(double x, int n)
{
if (n == 0)
return 1;
double a = power(x, n / 2); // 递归求x^(n/2)
if (n % 2 == 0)
return a * a;
else
return a * a * x;
}
};
四. 小结
此题为分治思路的经典题型之中的一个。
leetcode笔记:Pow(x, n)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。