更多題目移步【力扣簡單題】

題目

難度：★★☆☆☆
類型：數(shù)組

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

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

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

示例

示例 1:

輸入: 4
輸出: 2
示例 2:

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

解答

方案1：二分法

這道題目由于只要求取開平方后的整數(shù)部分，因此搜索范圍有限，可以考慮使用二分法。

1. 構(gòu)造數(shù)組從0到輸入x，該數(shù)組中每個元素與其所在位置相等，定義兩個指針，左指針left和右指針right，初始位置分別位于數(shù)組兩端；

2. 執(zhí)行循環(huán)，循環(huán)的控制條件是左指針不能跑到右指針的右邊去，每輪循環(huán)獲得中點所在位置，查看該數(shù)的平方s與輸入x之間的大小關(guān)系：
   （1）s == x：相當(dāng)于找到了開方結(jié)果，直接返回這個數(shù)；
   （2）s > x：平方結(jié)果較大，刪除數(shù)組右半部分
   （3）s < x：平方結(jié)果較小，刪除數(shù)組左半部分

3. 跳出循環(huán)時，返回右指針?biāo)谖恢谩?/p>

為何是右指針？如果一個數(shù)字x開平方x_quare不是整數(shù)，那么要跳出循環(huán)的前一個狀態(tài)一定是left=right或者left+1=right，不過無論如何left的位置都是n的向上取整，那么最后一個循環(huán)內(nèi)部所執(zhí)行的操作就必定是右指針左移到左指針左邊，也就是n的向下取整。

class Solution:
    def mySqrt(self, x):
        # 首先，我們構(gòu)造一個數(shù)組，數(shù)組中的每個值即為其所在位置（下標(biāo)），數(shù)組范圍是從0到x
        left, right = 0, x                          # 初始化左指針和右指針為數(shù)組兩端數(shù)字

        while left <= right:                        # 要求左指針不大于又指針，當(dāng)滿足條件時執(zhí)行
            # 求取中點位置（位置即為該位置的數(shù)），如果數(shù)組長度為偶數(shù)，取中間偏左的一個
            mid = left + (right - left) // 2

            if mid ** 2 > x:                        # 如果中點的平方大于輸入x
                right = mid - 1                     # 拋棄數(shù)組右半部分
            elif mid ** 2 < x:                      # 如果中點的平方小于輸入x
                left = mid + 1                      # 拋棄數(shù)組左半部分
            else:                                   # 如果中點的平方即為輸入x
                return mid                          # 直接返回中點即可

        return right                                # 返回結(jié)果

方案2：牛頓法

假設(shè)我們要求b的平方根，相當(dāng)于求的解，或者說，是函數(shù)與x軸的交點坐標(biāo)，我們使用牛頓法計算估算這個坐標(biāo)。

如圖所示是牛頓法的流程示意圖，假設(shè)我們要計算b=10的平方根，構(gòu)造函數(shù)，求該函數(shù)與x軸交點的橫坐標(biāo)，我們首先尋找在曲線上的一個點，點的橫坐標(biāo)為10，做這個點的切線，該切線與x軸有一個交點，然后過該點做垂線，與曲線又有一個交點，再次沿著該點做切線，重復(fù)上述流程，很顯然，隨著迭代的進行，垂線與曲線的交點（即下一輪的切點）會不斷逼近曲線與x軸的交點，當(dāng)垂線與曲線的交點的縱坐標(biāo)小于一定閾值時，我們將這個切點的橫坐標(biāo)近似認(rèn)為是曲線與x軸交點的橫坐標(biāo)。

牛頓法求取平方根

我們的工作就是每次尋找下一輪切點的坐標(biāo)。假設(shè)當(dāng)前切點的坐標(biāo)為，根據(jù)拋物線導(dǎo)數(shù)公式可得，該切點出切線的斜率為，設(shè)切線與x軸交點為，那么根據(jù)直線的斜率定義，可以得到：

解得：

那么過該交點作垂線后與曲線的交點縱坐標(biāo)為：

下一個切點的坐標(biāo)即為

不斷比較當(dāng)前切點縱坐標(biāo)與零之間的差值，當(dāng)小于某一閾值時，結(jié)束循環(huán)。

class Solution:
    def mySqrt(self, x):

        b = x                               # 改寫一下，顯得更清楚
        x_c, y_c = b, b * b - b             # 初始化切點坐標(biāo)
        while abs(y_c) > 1e-4:              # 滿足閾值條件
            x_n = x_c - y_c / (2 * x_c)     # 計算下一個切點橫坐標(biāo)，推導(dǎo)公式見上文
            y_n = x_n * x_n - b             # 計算下一個切點縱坐標(biāo)，推導(dǎo)公式見上文
            x_c, y_c = x_n, y_n             # 更新當(dāng)前坐標(biāo)

        return int(x_c)                     # 取出結(jié)果的整數(shù)部分即可

如有疑問或建議，歡迎評論區(qū)留言~