解答
1.我的方法
class Solution:
def mySqrt(self, x: int) -> int:
divisor = 1
if x == 0:
return 0
while divisor <= x:
solu = x // divisor
if abs(solu - divisor) <= 1:
return min(solu, divisor)
divisor += 1
不过超出时间限制了。。。这应该是O（n）叭，不知道为啥超出了。
改进一下，将while的条件设为divisior <= x/2。因为一般而言x的平方根不大于它的一半。但是存在个例。x=1,2,3时x的平方根会大于它的一半，就单独讨论。改进后如下：
def mySqrt(x):
divisor = 1
if x == 0:
return 0
if x == 2 or x == 3 or x == 1:
return 1
while divisor <= x/2:
solu = x // divisor
if abs(solu - divisor) <= 1:
return min(solu, divisor)
divisor += 1
依旧超出时间范围，fine
2.二分法
def mySqrt(self, x: int) -> int:
left = 0
right = x//2
if x == 0:
return 0
while left <= right:
# 一定要取右中点，不能取左中点，不然可能进入死循环（4和1的中点是2或3）
mid = (left + right + 1) >> 1 # 取右中点
# mid = left + (right - left + 1) // 2 # 取左中点
square = mid * mid
if square <= x:
left = mid
else:
right = mid - 1
return left
well，超出时间范围.....
3.牛顿法
设f(x) = x^2 - a. 这里a就是输入的值，x就是输出的平方根值。
https://blog.csdn.net/batuwuhanpei/article/details/51979831
https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/
讲解了牛顿法原理
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
cur = 1 # 随意定一个正的初值
pre = 0
while abs(cur - pre) >= 1e-6:
pre = cur
cur = pre - (pre * pre - x) / (2 * pre)
return int(cur)
