8-50.Pow(x,n)
題目描述:
解題思路:
第一想法是遞歸,結果
f(x,n) = x * f(x,n-1);
這種方法的空間複雜度太高了,太想當然。看了下題解:採取分治的方法:
f(x,n) = f(x,n/2) * f(x,n/2)
;這裡只需要注意一下n的奇偶性就可以,如果是偶數,就是這個式子,如果是奇數,需要額外多乘一個x;這樣空間複雜度就從O(N)轉成了O(logN);主要是分治和遞歸
程式碼:
class Solution {
public double myPow(double x, int n) {
long N = n;//當n是-intMIN的時候,轉換成正數會溢出、常用的辦法是轉成long類型的數據
//處理一些特殊情形
if(x == 0){
return 0;
}
if(N == 0){
return 1;
}
if(N > 0){
return powHelper(x,N);
}else{
return 1.0/powHelper(x,-N);
}
}
public double powHelper(double x,long N){
if(N == 1){//定義該函數出口
return x;
}
//分解成奇數和偶數兩個子問題,然後進行遞歸
if(N % 2 == 0){//當n為偶數
double half = powHelper(x,N/2);
return half * half;
}else{//n為奇數
double half = powHelper(x,N/2);
return half * half * x;
}
}
}