剑指offer 专项突破版（剑指OfferII072.求平方根）
给定一个非负整数 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的平方根
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
