LeetCode 69. x 的平方根

LeetCode 69. x 的平方根 | Python

69. x 的平方根

题目来源：https://leetcode-cn.com/problems/sqrtx

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解题思路

思路：二分查找

二分查找，也叫折半查找，相信从一个例子中能很好的理解这个概念。【猜数字】，可能很多人都接触过这个游戏。这里面就能够用二分查找进行实现。

当告知在谜底数字在一定的范围内，如何能够高效的猜中数字？那么二分查找这个方法在这里，就应该从这个范围内的中间开始猜测。当告知猜测的数字比谜底数字大或者小，进而判断谜底落在这个猜测数字的左侧还是右侧，再次确定范围后，又从中间开始猜测，循环直至猜出谜底数字。

题目中说明，x 为非负整数，从这个的角度来看，平方根是一定不会超过自身。同样，一个数的平方根与一个数的一半相比，数的平方根同样不会超过数的一半。

如果上面段内容后面部分不太能理解的话，可以尝试在纸上画出二次幂函数图像。所画出的曲线中的点，对应 x 轴的值其实就是 y 对应的值的平方根。当 y 值越大时，上面段内容的结论越明显。（注意：题目要求数为非负整数，即是 y 的取值。）

那么有以下不等式：

$\left(\frac{x}{2}\right)^2 \geq x$

解上面不等式，可得 $x \leq 0$ 或者 $x \geq 4$ 。

这里表示，如果数的一半的平方大于自身，那么这个数的取值范围。

可以看出这个边界值是 4，那么就对 0，1，2，3，单独进行计算。由于题目要求返回整数，小数部分将被舍去，那么对应的平方根依次是 0,1,1,1。

具体代码如下。

代码实现

class Solution:
    def mySqrt(self, x: int) -> int:
        # 注意边界 0, 1
        left = 0
        right = x // 2 + 1

        # 根据上面的公式进行计算
        # 开始进行二分查找
        while left < right:
            # 取中间值
            # 这里要取右中间值，不然会进入死循环
            mid = (left + right + 1) // 2
            square = mid * mid
            
            if square == x:
                return mid
            elif square > x:
                right = mid - 1
            else:
                left = mid
        return left

实现结果

以上就是使用二分查找的方法，解决《69. x 的平方根》问题的主要内容。

欢迎关注微信公众号《书所集录》