为了更好的明天,坚持刷 LeetCode

题目

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

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

解法一 - 二分查找

解题思路

x 的平方根就是要找到满足 $k^2 ≤ x$ 的最大 $k$ 值就可以了。

对 $k$ 进行二分查找,left 设为 0,right 设为 xmidleft + right 的平均值,通过比较调整 leftright

代码

func mySqrt(x int) int {
    if x == 0 {
        return 0
    }
    l, r := 0, x
    res := -1
    for l <= r {
        m := (l + r) / 2
        if m * m <= x {
            res = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return res
}

执行结果

执行用时:4 ms,在所有 Go 提交中击败了 52.52% 的用户
内存消耗:2.2 MB,在所有 Go 提交中击败了 61.82% 的用户

复杂度分析

  • 时间复杂度:$O(log x)$,二分查找需要的次数。
  • 空间复杂度:$O(1)$

题目链接

69. x 的平方根