【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)

• 作者主页： 🔗进朱者赤的博客

• 精选专栏：🔗经典算法

• 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

• ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞

  ————————————————-

  x 的平方根

  • 标签(题目类型)：数学、二分查找

    题目描述

    实现 int sqrt(int x) 函数。

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

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

    示例 1:

    输入: 4
    输出: 2
    

    示例 2:

    输入: 8
    输出: 2
    解释: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
    

    原题：LeetCode 69. x 的平方根

    思路及实现

    方式一：二分查找

    思路

    由于平方根函数的性质，我们知道平方根一定位于0和x之间（x为非负整数）。因此，我们可以使用二分查找算法在0到x之间查找平方根。在每次迭代中，我们计算中间值mid的平方，如果它等于x，则mid就是平方根；如果它小于x，则平方根一定在mid的右侧；如果它大于x，则平方根一定在mid的左侧。通过不断缩小查找范围，最终我们可以找到平方根。

    代码实现

    Java版本

    public class Solution {
        public int mySqrt(int x) {
            if (x  int:
            if x == 0: return 0
            last = 0.0
            curr = x
            epsilon = 0.00001
            while abs(curr - last) > epsilon:
                last = curr
                curr = (curr + x / curr) / 2
            return int(curr)
    

    说明：

    • Python版本同样使用了牛顿迭代法。
    • 使用了abs函数来计算浮点数之间的绝对值。

      Golang版本

      package main
      import (
      	"math"
      )
      func mySqrt(x int) int {
      	if x == 0 {
      		return 0
      	}
      	last := 0.0
      	curr := float64(x)
      	epsilon := 0.00001
      	for math.Abs(curr-last) > epsilon {
      		last = curr
      		curr = (curr + float64(x)/curr) / 2
      	}
      	return int(curr)
      }
      func main() {
      	// 测试代码
      	x := 8
      	result := mySqrt(x)
      	println(result) // 输出应为 2
      }
      

      说明：

      • Golang版本使用了牛顿迭代法来计算平方根。
      • epsilon定义了收敛的阈值，当连续两次迭代结果的差值小于这个阈值时，认为找到了足够精确的解。
      • math.Abs函数用于计算浮点数之间的绝对值。

        复杂度分析

        • 时间复杂度：与选择的阈值epsilon有关，但通常很快收敛，所以时间复杂度相对较低。
        • 空间复杂度：O(1)，只使用了常数级别的额外空间。

          总结

          方法	优点	缺点	时间复杂度	空间复杂度	其他
          二分查找	思路简单，直观易懂	可能不是最优解，对于非整数平方根需要额外处理	O(log x)	O(1)	适用于整数平方根计算
          牛顿迭代	收敛速度快，通常很快能得到近似解	需要选择合适的初始值和阈值	近似O(1)	O(1)	适用于需要高精度或浮点数平方根计算

          相似题目

          相似题目	难度	链接
          平方根的四舍五入	中等	力扣-6905
          求一个数的立方根	中等	力扣-69
          计算整数除法	简单	力扣-7
          计算平方和	简单	力扣-665
          最近的平方数	简单	力扣-676

          这些题目都涉及到数学运算和数值计算，与平方根计算有一定的相似性，可以用于加深对数值计算和相关算法的理解。请注意，这里提供的链接是基于假设的，实际链接需要根据具体的在线编程平台（如力扣）进行查找。

          欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

          • 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

          • —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—

手机扫描二维码访问