力扣69.x的平方根

发表于 更新于 分类于 Changyan：

题目

实现 int sqrt(int x) 函数。

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

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

示例 1:

1
2
输入: 4
输出: 2

示例 2:

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

链接：

https://leetcode-cn.com/problems/sqrtx/

解答

二分查找

二分法是符合计算机思想的解法。

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 bit 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        small = 1
        big = x
        while big - small > 1:
            bit = (small + big) // 2
            if bit ** 2 == x:
                return bit
            elif bit ** 2 < x:
                small = bit
            elif bit ** 2 > x:
                big = bit

        return int(small)

牛顿法

这个题解说的比较好：

https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/

该方法比较适合机器学习背景。

1
2
3
4
5
6
class Solution:
    def mySqrt(self, x: int) -> int:
        r = x
        while r * r > x:
            r = (r + x / r) // 2
        return int(r)