首页 > 代码库 > LeetCode 50. Pow(x, n)

LeetCode 50. Pow(x, n)

2024-08-17 22:34:44   215人阅读

Implement pow(x, n).

【题目分析】

实现幂指数函数。

【思路】

1. 防止overflow的发生

2. 减少时间复杂度

最简单的思路就是遍历啦，但是当n < 0时，有人会把n先变为-n，这样当n = Integer.MIN_VALUE是会产生溢出。

直接遍历相乘的时间复杂度很高，比如下面的方法是O(N)的复杂度：

1 public class Solution {
2     public double myPow(double x, int n) {
3         if(n == 0) return 1;
4         else if(n > 0) return x*myPow(x, n-1);
5         else return 1/x*myPow(x, n+1);
6     }
7 }

一种O(logN)时间复杂度的方法如下：

1 public class Solution {
2     public double myPow(double x, int n) {
3         if(n == 0) return 1.;
4         double res = myPow(x, n / 2);
5         return n % 2 == 0 ? res * res : n < 0 ? res * res * (1 / x) : res * res * x;
6     }
7 }

技术分享

 

LeetCode 50. Pow(x, n)


联系
我们