LeetCode Pow(x, n)

LeetCode Pow(x, n)

Implement pow(x, n).


实现幂指数运算。

如果对x连乘n次,时间复杂度为O(n),但使用分治法能降到O(\log n)。因为可以把x^n分解为:

\begin{equation*} x^n= \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \text{if } n \text{ even}\\ x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x, & \text{if } n \text{ odd} \end{cases} \end{equation*}

完整代码如下:

class Solution {
public:
	double doPow(double x, int n) {
		if (n == 0)return 1.0;
		double v = doPow(x, n / 2);
		if (n % 2 == 0)return v*v;
		else return v*v*x;
	}
	double myPow(double x, int n) {
		int m = n > 0 ? n : -n;
		double ans = doPow(x, m);
		return n > 0 ? ans : 1.0 / ans;
	}
};

本代码提交AC,用时3MS。

注意在子程序中不要调用两次doPow(x, n/2),算出一个v,然后直接v*v即可。

二刷。使用非递归的方法实现快速幂,代码如下:

class Solution {
public:
	double myPow(double x, int n) {
		if (n == 0) return 1;
		if (n == 1) return x;
		long long m = n; // 先转换为ll,否则n=INT_MIN是有问题
		m = m > 0 ? m : -m;
		double ans = 1;
		while (m) {
			if (m & 1)ans *= x;
			m >>= 1;
			x = x*x;
		}
		return n > 0 ? ans : 1 / ans;
	}
};

本代码提交AC,用时3MS。

One thought on “LeetCode Pow(x, n)

  1. Pingback: hihoCoder 1504-骑士游历 | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *