题目描述
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
解法一:二分查找
当 x=0
时,返回 0;
当 left > right
时,循环结束,此时,left ** 2 > x
,right ** 2 <= x
,所以返回 right
。
class Solution:
def mySqrt(self, x: int) -> int:
left, right= 1, x
while left <= right:
mid = left + (right - left) // 2
# 避免乘法溢出,改用除法
if mid <= x / mid:
left = mid + 1
else:
right = mid - 1
return right
解法二:牛顿迭代
牛顿迭代法能快速求解函数零点的近似值。
假设 X 是待求平方根的整数,X的平方根就是函数
\[f(x) = x^2-X \]的零点。
而我们可以用牛顿迭代法快速逼近函数零点。
因为 \(f'(x)=2x\),所以
\[\begin{align} x_{k+1} &= x_k - \frac{x_k^2-X}{2x_k} \\ &= \frac{1}{2}(x_k+\frac{X}{x_k}) \end{align} \]class Solution:
def mySqrt(self, x: int) -> int:
res = x
while res * res > x:
res = (res + x // res) // 2
return (int)res
标签:right,int,res,整数,算法,平方根,left
From: https://www.cnblogs.com/hzyuan/p/18075437