描述:
实现函数int sqrt(int x)
计算并返回x的平方根(向下取整)
数据范围:\(0 \le x \le 2^{31} - 1\),要求空间复杂度$ o(1) \(,时间复杂度\)o(logx) $.
示例1:
输入:
2
返回值:
1
示例2:
输入:
2143195649
返回值:
46294
思路: 二分查找方法
代码:
class Solution:
def sqrt(self , x: int) -> int:
# write code here
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
标签:le,示例,int,复杂度,sqrt,平方根
From: https://www.cnblogs.com/bonne-chance/p/18087554