题目描述

[EN | CN]

实现 int sqrt(int x) 函数。

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

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

示例 1:

1
2
输入: 4
输出: 2

示例 2:

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

解法 1:二分查找

二分查找即可。注意如果中间索引 m 算出来的 m ** 2x 小的时候,我们将 m 赋给结果的候选值(例如 3^2 < 10 < 4^2,所以结果应该是 3)。

复杂度如下

  • 时间复杂度为 $O(\log x)$,二分查找;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ret = 0, x, -1
        while l <= r:
            m = (l + r) // 2
            s = m ** 2
            if s < x:
                ret = m
                l = m + 1
            elif s > x:
                r = m - 1
            else:
                return m
        return ret
  • 执行用时:52 ms,在所有 Python3 提交中击败了 53.45% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 6.06% 的用户。