剑指 Offer II 072. 求平方根
小于 1 分钟
剑指 Offer II 072. 求平方根
- 标签:数学、二分查找
- 难度:简单
题目链接
题目大意
要求:实现 int sqrt(int x)
函数。计算并返回 x
的平方根(只保留整数部分),其中 x
是非负整数。
解题思路
因为求解的是 x 开方的整数部分。所以我们可以从 0~x 的范围进行遍历,找到 k^2 <= x 的最大结果。
为了减少时间复杂度,使用二分查找的方式来搜索答案。
代码
class Solution:
def mySqrt(self, x: int) -> int:
left = 0
right = x
ans = -1
while left <= right:
mid = (left + right) // 2
if mid * mid <= x:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans