给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例

输入:x = 8  输出:2

输入:x = 4  输出:2

解析

1)不允许使用内置指数函数,而且会舍弃小数部分,不是精准值,说明只能挨个尝试了

2)挨个尝试,数字大小相关的问题,都可以考虑二分查找,速度更快

代码示例

def mySqrt(self, x: int) -> int:
    left = 0
    right = x
    while left <= right:
        mid = (left + right) // 2
        s = mid * mid
        if s < x:
            left = mid + 1
        elif s > x:
            right = mid - 1
        else:
            return mid
    return left - 1

print(mySqrt(8))

执行用时:36 ms, 在所有 Python3 提交中击败了 92.45% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/364