剑指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)

剑指offer 专项突破版(剑指OfferII072.求平方根)(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

    分享
    投诉
    首页