leetcode.69.求一個數的平方根
題目描述
實現 int sqrt(int x) 函式。
計算並返回 x 的平方根,其中 x 是非負整數。
由於返回型別是整數,結果只保留整數的部分,小數部分將被捨去。
示例1:
輸入: 4 輸出: 2
示例2:
輸入: 8 輸出: 2 說明: 8 的平方根是 2.82842..., 由於返回型別是整數,小數部分將被捨去。
暴力版本
// 暴力解法 func mySqrt(x int) int { for i := 0; i <= x; i++ { res := i * i if res == x { return i } else if res > x { return i - 1 } } return -1 }
二分查詢
//在有序陣列中,找到最後一個小於等於給定值的數 func mySqrt2(x int) int { low, high := 0, x for low <= high { //防止大數相加溢位 //位運算更高效 mid := low + (high-low)>>1 product := mid * mid if product > x { high = mid - 1 } else { if (mid == x) || (mid+1)*(mid+1) > x { //遍歷最後一個數 || 下一個數大於目標值 return mid } //下一個數小於等於目標值,所以mid不是最後一個數 low = mid + 1 } } return -1 }
二分查詢思路
- 相當於從0-x中找到最後一個平方<=x的整數
- 我們求解的是最後一個小於等於給定值的元素,所以當 product<=x時,需要確認 mid+1 的平方>x
- 如果 mid+1 的平方 <= x ,說明mid肯定不是最後一個,更新low
GitHub
- ofollow,noindex" target="_blank">戳這裡看原始碼
- 各種資料結構及演算法的Golang實現, LeetCode解題思路及答案
- 大廠面試題彙總及答案解析
參考資料
本文為原創文章,轉載註明出處,歡迎掃碼關注公眾號tomorrowwu
或者網站https://lovecoding.club
,第一時間看後續精彩文章,覺得好的話,順手分享到朋友圈吧,感謝支援。