【問題描述】

實現 int sqrt(int x) 函數。計算并返回 x 的平方根，其中 x 是非負整數。由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。輸入: 8 輸出: 2 說明: 8 的平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。

【解答思路】

1. 二分法（面試必備）

1.1 縮小邊界 x/2
時間復雜度：O(logN) 空間復雜度：O(1)

Java 代碼要注意到：如果中點 mid 聲明為 int 類型，針對大整型測試用例通不過，因此變量需要聲明為 long 類型。

public class Solution {public int mySqrt(int x) {// 注意：針對特殊測試用例，例如 2147395599// 要把搜索的范圍設置成長整型// 為了照顧到 0 把左邊界設置為 0long left = 0;// # 為了照顧到 1 把右邊界設置為 x // 2 + 1long right = x / 2 + 1;while (left < right) {// 注意：這里一定取右中位數，如果取左中位數，代碼會進入死循環// long mid = left + (right - left + 1) / 2;long mid = (left + right + 1) >>> 1;long square = mid * mid;//畫圖排除法思想 現象最簡單的 if (square > x) {right = mid - 1;} else {left = mid;}}// 因為一定存在，因此無需后處理return (int) left;}}

1.2 常規思路 零神筆法

時間復雜度：O(logN) 空間復雜度：O(1)

class Solution {public int mySqrt(int x) {int l = 0, r = x, ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if ((long)mid * mid <= x) {ans = mid;l = mid + 1;}else {r = mid - 1;}}return ans;} }

2.牛頓法

牛頓法得到的是平方根的浮點型精確值（可能會有一定誤差），根據題目中的要求，把最后得到的這個數轉換為 int 型，即去掉小數部分即可


時間復雜度：O(logN) 空間復雜度：O(1)

public class Solution {public int mySqrt(int a) {long x = a;while (x * x > a) {x = (x + a / x) / 2;}return (int) x;} }

3. 袖珍計算器算法 零神提供新思路

時間復雜度：O(logN) 空間復雜度：O(1)

class Solution {public int mySqrt(int x) {if (x == 0) {return 0;}int ans = (int)Math.exp(0.5 * Math.log(x));return (long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans;} }

4. 庫函數 皮一下很開心

public int mySqrt(int x) {return (int)Math.sqrt(x);}

【總結】

1. 一題多解 樂趣多

2.二分法 注意細節

3. 一人之下 真好看

參考鏈接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
參考鏈接：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第69题][x的平方根][二分查找][数学]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。