---

---

69. x 的平方根：

給你一個非負整數 x ，計算并返回 x 的 算術平方根 。

由于返回類型是整數，結果只保留 整數部分 ，小數部分將被 舍去 。

注意：不允許使用任何內置指數函數和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

樣例 1：

輸入：x = 4輸出：2

樣例 2：

輸入：x = 8輸出：2解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。

提示：

• 0 <= x <= 2³¹ - 1

---

分析：

• 面對這道算法題目，二當家的再次陷入了沉思。
• 要開平方，但是不允許使用內置的指數函數，這是故意難為我胖虎。
• 暴力破解，反正只要整數，從 1 到 x ，一個一個試，就能找到最接近的解，很簡單，但是過于簡單了，一定還有更好的辦法。
• 答案只要整數，從線性連續的數值里找最優，想到可以用二分查找法，不斷嘗試，二分查找的效率很高，每次都能減少一半的數據量，已經可以滿意了。
• 還有一個更好的辦法，答案要的是近似的整數，所以還可以使用 牛頓迭代法 ，非常適合高效找到近似解，聽說效率比二分查找還高。
• 感覺數學還是厲害啊，很多東西都是可以用數學的方法高效解決的，雖然計算機已經很快了，但是很多時候用數學的方式去解決，可以快上加快，很想學好數學。
• 下面的題解都是使用 牛頓迭代法，找近似解，所以需要有個度，一個停止繼續的點，一般認為兩次連續求得的解的差非常小的時候，就是應該停止繼續循環的時候，我們這里使用 e^-7 作為兩次求解的檢查。

---

題解：

rust：

impl Solution {pub fn my_sqrt(x: i32) -> i32 {if x == 0 {return 0;}let (c, mut x0) = (x as f64, x as f64);loop {let xi = 0.5 * (x0 + c / x0);if (x0 - xi).abs() < 1e-7 {break;}x0 = xi;}return x0 as i32;}
}

---

go：

func mySqrt(x int) int {if x == 0 {return 0}c, x0 := float64(x), float64(x)for {xi := 0.5 * (x0 + c/x0)if math.Abs(x0-xi) < 1e-7 {break}x0 = xi}return int(x0)
}

---

c++：

class Solution {
public:int mySqrt(int x) {if (x == 0) {return 0;}double c = x, x0 = x;while (true) {double xi = 0.5 * (x0 + c / x0);if (fabs(x0 - xi) < 1e-7) {break;}x0 = xi;}return int(x0);}
};

---

python：

class Solution:def mySqrt(self, x: int) -> int:if x == 0:return 0c, x0 = float(x), float(x)while True:xi = 0.5 * (x0 + c / x0)if abs(x0 - xi) < 1e-7:breakx0 = xireturn int(x0)

---

java：

class Solution {public int mySqrt(int x) {if (x == 0) {return 0;}double c = x, x0 = x;while (true) {double xi = 0.5 * (x0 + c / x0);if (Math.abs(x0 - xi) < 1e-7) {break;}x0 = xi;}return (int) x0;}
}

---

非常感謝你閱讀本文~
歡迎【點贊】【收藏】【評論】三連走一波~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子：https://le-yi.blog.csdn.net/ 博客原創~

---