题目

给定一个非负整数 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的平方根