欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(python刷题)leetcode 第69题:x的平方根

程序员文章站 2022-06-17 19:12:46
...

题目描述:
(python刷题)leetcode 第69题:x的平方根

解题思路:
求平方根的问题用牛顿法解题较好。牛顿法通过不断迭代求得方程的近似解。要求sqrt(a),相当于求函数f(x)=x2-a的正根,牛顿法的思路是先随便初始化一个点(xn,f(xn)),然后求函数在该点的切线与x轴的交点xn+1,则xn+1是比xn更加接近所求解的,依次迭代下去就可以得到近似解。下面用一张图较为直观的进行说明:
(python刷题)leetcode 第69题:x的平方根
图像的曲线方程为y=x2-a,为了求它的正根sqrt(a),我们先随便初始化曲线上的一个点A(xn,f(xn)),在A点做曲线的切线,切线与x轴的交点为B(xn+1,0),从图中可以看到xn+1比xn更接近所求的解,那么继续在B点做切线重复以上过程,就可以得到一个更接近的解,不断迭代,直接得到的解在所需要的误差范围内即可找到所求的近似解。
下面推导迭代的公式:
(python刷题)leetcode 第69题:x的平方根
得到的迭代公式就好办了,牛顿法的解题步骤为:

  1. 先对特殊情况进行判断,当x=0时,直接返回0
  2. 题目给的x就是公式里的a,初始化x0=x,x0的下一个迭代的值为
    x1=(x0+x/x0)/2
  3. 判断得到的x1是否在所需的误差范围内,这里要返回整数,所以误差为1,即判断abs(x1**2-x)是否小于1,如果是则返回int(x1)即可
  4. 如果不是,则继续迭代下去,直到x1在误差范围才返回int(x1)

复杂度分析:
时间复杂度为o(log(x))
空间复杂度为o(1)

python代码:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return x
        x0 = x
        x1 = (x0 + x / x0) / 2
        while abs(x1 ** 2 - x) >= 1:
            x0 = x1
            x1 = (x0 + x / x0) / 2
        return int(x1)