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

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

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 < 2) return x; // 特殊情况处理
        long left = 2; // 左边界设为2,因为1的平方根为1,无需查找
        long right = x / 2; // 右边界设为x/2,因为平方根不会大于x/2
        while (left <= right) {
            long mid = left + (right - left) / 2; // 防止溢出
            long square = mid * mid;
            if (square == x) {
                return (int) mid;
            } else if (square < x) {
                left = mid + 1; // 平方根在mid右侧
            } else {
                right = mid - 1; // 平方根在mid左侧
            }
        }
        // 因为我们查找的是小于等于x的最大的平方根,所以返回right
        return (int) right;
    }
}

说明:

  • 使用long类型进行中间计算,防止整数溢出。
  • square等于x时直接返回结果。
  • 如果square小于x,则平方根一定在mid的右侧,因此更新左边界为mid + 1
  • 如果square大于x,则平方根一定在mid的左侧,因此更新右边界为mid - 1
  • 最终返回的是right,因为在循环结束时,right会指向小于等于x的最大的平方根。
C语言版本
#include <math.h>
int mySqrt(int x) {
    if (x < 2) return x;
    long left = 2;
    long right = x / 2;
    while (left <= right) {
        long mid = left + (right - left) / 2;
        long square = mid * mid;
        if (square == x) {
            return (int)mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return (int)right;
}

说明:

  • 与Java版本类似,C语言版本也使用了二分查找的思想。
  • 使用了long类型进行中间计算以避免溢出。
Python3版本
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2: return x
        left = 2
        right = x // 2
        while left <= right:
            mid = (left + right) // 2
            square = mid * mid
            if square == x:
                return mid
            elif square < x:
                left = mid + 1
            else:
                right = mid - 1
        return right

说明:

  • Python版本同样采用了二分查找的思路。
  • 由于Python整数运算不会溢出,这里不需要使用额外的数据类型来避免溢出。
Golang版本
package main
import (
  "math"
)
func mySqrt(x int) int {
  if x < 2 {
    return x
  }
  left := 2
  right := x / 2
  for left <= right {
    mid := left + (right-left)/2
    square := mid * mid
    if square == x {
      return mid
    } else if square < x {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return right
}
func main() {
  // 测试代码
  x := 8
  result := mySqrt(x)
  println(result) // 输出应为 2
}

说明:

  • Golang版本同样使用了二分查找的思想来计算平方根。
  • leftright分别表示查找范围的左右边界。
  • 在循环中,根据中间值mid的平方与x的比较结果来更新查找范围。
  • 最终返回right,它是小于等于x的最大的平方根。

复杂度分析

  • 时间复杂度:O(log x),因为每次迭代都将查找范围减半。
  • 空间复杂度:O(1),只使用了常数级别的额外空间。

方式二:牛顿迭代法

思路

牛顿迭代法是一种在实数上近似求解方程的方法。对于平方根的计算,我们可以使用牛顿迭代法的公式, 来不断逼近平方根的值。

牛顿迭代法的公式可以表示为:

xₙ₊₁ = xₙ - f(xₙ) / f’(xₙ)

其中,xₙ是第n次迭代的解, xₙ₊₁是第n+1次迭代的解, f(xₙ)是函数在xₙ处的函数值, f’(xₙ)是函数在xₙ处的导数值。

这个公式用于不断逼近函数的根,直到满足一定的精度要求。

代码实现

Java版本
public class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        double last = 0, curr = x;
        while (Math.abs(curr - last) > 0.00001) {
            last = curr;
            curr = (curr + x / curr) / 2;
        }
        return (int) curr;
    }
}

说明:

  • 初始化last为0,currx
  • 在循环中,根据牛顿迭代法的公式更新curr的值。
  • currlast的差值小于某个很小的阈值时,认为找到了足够接近的解,跳出循环。
  • 返回curr的整数部分作为结果。
C语言版本
#include <math.h>
int mySqrt(int x) {
    if (x == 0) return 0;
    double last = 0, curr = x;
    double epsilon = 0.00001;
    while (fabs(curr - last) > epsilon) {
        last = curr;
        curr = (curr + x / curr) / 2;
    }
    return (int)curr;
}

说明:

  • C语言版本与Java版本类似,使用了牛顿迭代法来逼近平方根。
  • 使用了fabs函数来计算浮点数之间的绝对值。
Python3版本
class Solution:
    def mySqrt(self, x: int) -> 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

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

相关文章
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
4天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现GWO智能灰狼优化算法优化支持向量机回归模型(svr算法)项目实战
Python实现GWO智能灰狼优化算法优化支持向量机回归模型(svr算法)项目实战