给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
示例 1:输入: x = 4 输出: 2
示例 2:输入: x = 8 输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
提示:0 <= x <= 231 - 1
注意：本题与主站 69 题相同：
解题思路分析1、内置函数；时间复杂度O(log(n))，空间复杂度O(1)
func mySqrt(x int) int {
result := int(math.Sqrt(float64(x)))
return result
}
2、内置函数；时间复杂度O(log(n))，空间复杂度O(1)
func mySqrt(x int) int {
result := math.Floor(math.Sqrt(float64(x)))
return int(result)
}
3、牛顿迭代法；时间复杂度O(log(n))，空间复杂度O(1)
func mySqrt(x int) int {
result := x
for result*result > x {
result = (result x/result) / 2
}
return result
}
4、二分查找；时间复杂度O(log(n))，空间复杂度O(1)
func mySqrt(x int) int {
left := 1
right := x
for left <= right {
mid := (left right) / 2
if mid == x/mid {
return mid
} else if mid < x/mid {
left = mid 1
} else {
right = mid - 1
}
}
if left*left <= x {
return left
} else {
return left - 1
}
}
5、遍历；时间复杂度O(n)，空间复杂度O(1)
func mySqrt(x int) int {
result := 0
for i := 1; i <= x/i; i {
if i*i == x {
return i
}
result = i
}
return result
}
Easy题目，题目同leetcode 69.x的平方根
,
