作者 | 陌無崖
轉載請聯系授權
題目要求
求一個數的整數次方
題目分析
通常我們會很輕松的寫出該題的思路，隻需要用一個for循環即可，如下：
func Power_one(data float64, n int) float64 {
sum := 1.0
for i := 1; i <= n; i++ {
sum *= data
}
return sum
}
複制
基于以上的思路，其實是有bug的，假如輸入的n為0或者小于0呢？是以我們需要對我們的代碼進行改進。若n < 0 ,其實我們求出的是一個倒數，即-n次方的倒數。那麼我們可以對我們的代碼進行如下改進，用一個标記sign記錄正負：
func Power_two(data float64, n int) float64 {
if n == 0 {
return 1.0
}
sign := 0
if n < 0 {
n = -n
sign = 1
}
sum := Power_one(data, n)
if sign == 1 && sum != 0 {
return 1.0 / sum
}
return sum
複制
在上面代碼我們需要注意的是sum如果為0時，因為0不可為分母，是以0的倒數沒有意義。傳回1和0都可，但面試時需要和面試官講清楚。
在上面的代碼中，其實還有一處不太完美，我們都知道浮點數中判斷兩個數相等時，不能直接使用 == ,因為在計算機中表示小數是有精度損失的，一般我們認為當兩個數相減時在一個很近的範圍我們即認為這兩個數相等。代碼如下：
func equal(num1, num2 float64) bool {
if num1-num2 > -0.0000001 && num1-num2 < 0.0000001 {
return true
}
return false
}
複制
代碼優化
對于上述代碼我們的時間複雜度為O(n),那有沒有時間複雜度更低的方法呢？舉個例子，假如我們要計算2^32,如果我們已經知道了2^16,是以我們隻需要在此基礎上進行平方即可，同樣如果我們知道了2^8,隻需要在此基礎上進行平方即可，按照這樣的思路我們可以寫出如下公式：
公式
是以我們可以把求整數次方的代碼寫成遞歸的模式，如下：
func Power_one__two(data float64, n int) float64 {
if n == 0 {
return 1.0
}
if n == 1 {
return data
}
sum := Power_one__two(data, n>>1)
sum *= sum
//判斷n為奇數還是偶數
if n&1 == 1 {
// 奇數
sum *= data
}
return sum
}
複制
在上面的代碼中我們了右移來代表除法，用了位操作與運算判斷奇偶性，提高我們代碼的運作效率，完整代碼如下：
// 降低時間複雜度優化
func Power_four(data float64, n int) float64 {
if n == 0 {
return 1.0
}
sign := 0
if n < 0 {
n = -n
sign = 1
}
sum := Power_one__two(data, n)
if sign == 1 && !equal(sum, 0.0) {
return 1.0 / sum
}
return sum
}
複制
檢視完整源碼可以點選閱讀原文進入github倉庫，如果喜歡，感謝你為我點一個星星^_^
END