[Easy]LeetCode#69. x 的平方根

[Easy]LeetCode#69. x 的平方根

题目原地址

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。
  • 基本算法,这个easy,比较简单就是二分的查找到这个整数就行
func mySqrt(x int) int {
    mMap := make(map[int]int)
    res := 0
    s := 1
    e := x
    n := 0
    for n < x {
        m := (s + e) / 2
        n = m * m
        if mMap[m] > 0 {
            break
        }
        mMap[m]++
        if n == x {
            res = m
            break
        } else if n < x {
            res = m
            s = m
        } else {
            e = m
            n = 0
        }
    }
    return res
}