題目

實(shí)現(xiàn) int sqrt(int x) 函數(shù)。

計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。

由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。

示例 1:

輸入: 4
輸出: 2

示例 2:

輸入: 8 輸出: 2 說(shuō)明: 8 的平方根是 2.82842…,
由于返回類型是整數(shù)，小數(shù)部分將被舍去。

二分法

我們要找的是滿足 ans * ans <= x 中ans的最大值。
以0位左邊界，x為右邊界開(kāi)始折半查找滿足情況的數(shù)。
由于題目要求的是向下取整的數(shù)，而最后不滿足while條件退出時(shí)的start已經(jīng)在原有的基礎(chǔ)上+1了，所以需要進(jìn)行-1操作。

class Solution { public:int mySqrt(int x) {int start = 0;int end = x;//int ans = 0;int mid = (start + end) / 2;while(start <= end){mid = (start + end) / 2;if((long long)mid*mid == x) return mid;else if((long long)mid*mid > x){end = mid - 1;}else {start = mid + 1;}}return start - 1;} };

牛頓迭代法

用一階泰勒展式（即在當(dāng)前點(diǎn)的切線）代替原曲線，求直線與 x 軸的交點(diǎn)，重復(fù)這個(gè)過(guò)程直到收斂。
迭代公式為：
x =0.5( x + a/x)

class Solution { public:int mySqrt(int x) {double cur = 1;double pre = 1;while(true){pre = cur;cur = (cur + x / cur) / 2;if(abs(pre - cur) < 1e-6)return (int)cur;}} };

總結(jié)

以上是生活随笔為你收集整理的leetcode 69. x 的平方根 思考分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。