 五种解法全解析：从暴力枚举到牛顿迭代)
LeetCode 69 Sqrt(x) 五种解法全解析从暴力枚举到牛顿迭代【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以当前仓库中的算法讲解文档 articles/sqrtx.md 为骨架系统拆解 LeetCode 69「Sqrt(x)」这一经典整数开方问题的五种解法暴力枚举、语言内建函数、二分查找、位运算递归与牛顿迭代法。文章同时结合仓库内 python/0069-sqrtx.py、cpp/0069-sqrtx.cpp、java/0069-sqrtx.java 等真实提交源码深入讲解每种算法的实现细节、复杂度与溢出陷阱。读完本文你将掌握整数平方根问题的完整解题思路并能针对不同约束条件选择最优解法。问题回顾给定一个非负整数x返回x的平方根并向下取整为最接近的整数。返回的整数也必须是非负的。注意题目禁止使用任何内建的指数函数或运算符例如 C 中的pow(x, 0.5)或 Python 中的x ** 0.5该约束在 cpp/0069-sqrtx.cpp 头部注释中明确给出。示例输入x 4输出2因为 4 的平方根是 2输入x 8输出2因为 8 的平方根向下取整为 2.82 → 2。从数学上看x的整数平方根就是满足i * i x的最大整数i这也是后续所有解法共同依赖的核心判定条件。前置知识在动手实现前需要熟悉以下四项基础能力它们分别对应文中五种解法所需的核心技巧二分查找Binary Search每次迭代将搜索空间减半是本题最优解解法三的基础整数溢出处理Integer Overflow Handling对较大的数求平方可能溢出 32 位整数需要用 64 位类型承载中间计算结果例如 Java 的long、C 的long long位运算Bit Manipulation递归解法解法四利用右移 2 位实现「除以 4」、左移 1 位实现「乘以 2」从而完成对搜索空间的缩放牛顿迭代法Newtons Method一种迭代数值技术收敛速度极快是解法五的理论基石。解法一暴力枚举Brute Force思路平方根就是满足i * i x的最大整数i。因此可以从1开始逐个检查每个整数直到某个整数的平方超过x此时上一个整数就是答案。算法步骤处理边界情况若x 0直接返回0初始化res 1用于记录潜在答案从1遍历到x对每个整数i检查i * i x是否成立若i * i x返回上一个有效结果res否则更新res i并继续遍历循环结束后返回res。复杂度时间复杂度$O(\sqrt{n})$——注意循环最多跑到 $\lfloor \sqrt{x} \rfloor$ 就返回而非x空间复杂度$O(1)$。该解法在x很大例如接近 $2^{31} - 1$时会超时仅作为思路铺垫实际提交需采用更高效的方案。解法二内建函数In-Built Function思路大多数编程语言都提供了内建的平方根函数底层通常使用牛顿迭代法或类似的优化数学算法实现。直接调用内建函数后对结果截断取整即可得到整数平方根。算法步骤调用语言内建的平方根函数计算x的浮点平方根将结果转换为整数截断小数部分返回该整数。各语言实现要点Pythonint(sqrt(x))注意先from math import sqrtJava / C#(int) Math.sqrt(x)/(int) Math.Sqrt(x)浮点转整型时自动截断JavaScriptMath.floor(Math.sqrt(x))使用floor显式向下取整Goint(math.Sqrt(float64(x)))需先转换为float64Rust(x as f64).sqrt() as i32。复杂度时间复杂度$O(1)$空间复杂度$O(1)$。注意虽然内建函数在普通场景下是 $O(1)$但本题要求不得使用内建指数/开方函数因此该解法仅用于理解思路正式提交应以解法三、五为准。解法三二分查找Binary Search——推荐解法思路整数的平方是单调递增的$0^2 1^2 2^2 \dots$满足二分查找的单调性前提。我们要找的是满足m * m x的最大m搜索空间为[0, x]每次根据中间值平方与x的大小关系收缩区间。算法步骤初始化左边界l 0、右边界r x、结果变量res 0当l r时循环计算中间值m l (r - l) / 2用减法代替加法进一步规避l r的溢出风险若m * m x答案必然更小令r m - 1若m * m xm是合法候选存入res继续向右寻找更大的值令l m 1若m * m x恰好找到精确平方根直接返回m循环结束返回res。各语言实现要点以文档中的 Python 实现为例class Solution: def mySqrt(self, x: int) - int: l, r 0, x res 0 while l r: m l (r - l) // 2 if m * m x: r m - 1 elif m * m x: l m 1 res m else: return m return res在 Java / C / Go / Rust 等强类型语言中m * m必须显式转换为 64 位类型再比较例如 Java 的(long) m * m、C 的(long long) m * m、Rust 的m as i64 * m as i64。Python 的整数无精度上限无需处理。仓库源码佐证仓库内多份提交均采用二分查找思路可以作为对照学习python/0069-sqrtx.py 采用mid * mid三分支二分循环退出后返回r此时r恰好是最后一个满足r * r x的值java/0069-sqrtx.java 维护probableAns变量记录候选答案仅当mid * mid x时才更新并右移左边界最终返回最后一次合法候选csharp/0069-sqrtx.cs 采用left right循环结束时返回left - 1c/0069-sqrtx.c 使用long int m承载中间值避免溢出javascript/0069-sqrtx.js 用 1完成除以 2并在循环内直接判断mid * mid x (mid 1) * (mid 1) x提前返回。各实现的循环退出条件与返回值略有差异但本质都是「寻找满足平方不超过x的最大整数」。复杂度时间复杂度$O(\log n)$空间复杂度$O(1)$。解法四位运算递归Recursion思路利用一个简洁的数学恒等式$$\sqrt{x} 2 \cdot \sqrt{x / 4}$$将x右移 2 位等价于除以 4得到更小的子问题递归求出sqrt(x / 4)后左移 1 位等价于乘以 2还原尺度最后检查结果加 1 是否仍合法从而确定精确的整数平方根。算法步骤基准情形若x 2直接返回x因为 $\sqrt{0} 0$、$\sqrt{1} 1$递归计算下界l mySqrt(x 2) 1计算候选值r l 1若r * r x返回l否则返回r。Python 实现class Solution: def mySqrt(self, x: int) - int: if x 2: return x l self.mySqrt(x 2) 1 r l 1 return l if r ** 2 x else r在 Kotlin 中对应写法为mySqrt(x shr 2) shl 1Java / C# / C 则为mySqrt(x 2) 1。各语言的位运算符语义一致 2除以 4 1乘以 2。复杂度时间复杂度$O(\log n)$——每层递归输入缩小为原来的 1/4空间复杂度$O(\log n)$——来自递归调用栈的深度。解法五牛顿迭代法Newtons Method思路牛顿迭代法是求解方程根的经典数值方法。为求 $\sqrt{x}$等价于求函数 $f(r) r^2 - x$ 的根。牛顿迭代公式给出更新规则$$r_{new} \frac{r x / r}{2}$$从初始猜测r x出发反复应用该公式直到r * r x即完成收敛此时r就是整数平方根。从 articles/sqrtx.md 的公式推导可见(r x / r) / 2等价于(r x // r) 1整数除法 右移 1 位这也是各语言实现统一采用右移的原因。算法步骤初始化r x作为初始猜测当r * r x时更新r (r x / r) / 2整数除法或等价地右移 1 位循环在r * r x时终止返回r作为整数平方根。Python 实现class Solution: def mySqrt(self, x: int) - int: r x while r * r x: r (r x // r) 1 return r注意 JavaScript 版本需使用Math.floor(x / r)保证整数除法语义Java / C# 中r声明为long防止平方溢出Kotlin 中x / r在Long类型下自动为整数除法。复杂度时间复杂度$O(\log n)$——牛顿迭代呈二次收敛迭代次数极少空间复杂度$O(1)$。从仓库源码看kotlin/0069-sqrtx.kt 在同一文件中同时给出了二分查找与牛顿迭代两份实现后者以while (i x / i)作为循环条件写法更紧凑可作为两种解法的对照参考。常见陷阱平方运算的整数溢出在二分查找中计算m * m时若m较大32 位整数下约 46340 的平方即接近溢出上限结果可能溢出 32 位整型导致错误比较。务必在乘法前转换为 64 位类型Java 使用(long) m * mC 使用(long long) m * mRust 使用m as i64 * m as i64Go 使用int64(m) * int64(m)。这一点在文档的 Pitfalls 章节和仓库各语言提交中均有体现——例如 cpp/0069-sqrtx.cpp 全程使用long long变量。二分查找中的边界Off-by-One错误一个隐蔽的错误是当m * m x时直接返回m而不再向右搜索。正确做法是把m记录为候选答案并继续向右扩展l m 1因为可能存在更大的合法值。循环结束后返回最后一次记录的候选结果。文档给出的二分模板解法三以及 java/0069-sqrtx.java 的probableAns模式都体现了这一要点。五种解法对比与选型建议解法核心技巧时间复杂度空间复杂度适用场景暴力枚举线性扫描$O(\sqrt{n})$$O(1)$仅用于理解问题定义内建函数语言库函数$O(1)$$O(1)$工程场景无禁用手限制二分查找单调性 分治$O(\log n)$$O(1)$面试/竞赛首选稳定可靠位运算递归数学恒等式 移位$O(\log n)$$O(\log n)$考察位运算与递归技巧牛顿迭代数值分析$O(\log n)$$O(1)$收敛最快体现数学功底从仓库的提交分布看见 README.md 中的完成度表格C、C、C#、Java、JavaScript、Kotlin、Python 均提供了本题的可运行实现其中二分查找是各语言提交的主流方案说明它是该题最具普适性与工程价值的答案。建议读者重点掌握解法三并理解解法五的迭代原理即可完整覆盖该题的考察要点。延伸阅读二分查找的更多变体可参考仓库文章 articles/binary-search.md位运算相关的另一经典题可参考 articles/sum-of-two-integers.md若希望查看本文五种解法的完整多语言代码请直接阅读 articles/sqrtx.md 原文并按需对照仓库内各语言的 0069-sqrtx 实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 69 Sqrt(x) 五种解法全解析：从暴力枚举到牛顿迭代
LeetCode 69 Sqrt(x) 五种解法全解析从暴力枚举到牛顿迭代【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以当前仓库中的算法讲解文档 articles/sqrtx.md 为骨架系统拆解 LeetCode 69「Sqrt(x)」这一经典整数开方问题的五种解法暴力枚举、语言内建函数、二分查找、位运算递归与牛顿迭代法。文章同时结合仓库内 python/0069-sqrtx.py、cpp/0069-sqrtx.cpp、java/0069-sqrtx.java 等真实提交源码深入讲解每种算法的实现细节、复杂度与溢出陷阱。读完本文你将掌握整数平方根问题的完整解题思路并能针对不同约束条件选择最优解法。问题回顾给定一个非负整数x返回x的平方根并向下取整为最接近的整数。返回的整数也必须是非负的。注意题目禁止使用任何内建的指数函数或运算符例如 C 中的pow(x, 0.5)或 Python 中的x ** 0.5该约束在 cpp/0069-sqrtx.cpp 头部注释中明确给出。示例输入x 4输出2因为 4 的平方根是 2输入x 8输出2因为 8 的平方根向下取整为 2.82 → 2。从数学上看x的整数平方根就是满足i * i x的最大整数i这也是后续所有解法共同依赖的核心判定条件。前置知识在动手实现前需要熟悉以下四项基础能力它们分别对应文中五种解法所需的核心技巧二分查找Binary Search每次迭代将搜索空间减半是本题最优解解法三的基础整数溢出处理Integer Overflow Handling对较大的数求平方可能溢出 32 位整数需要用 64 位类型承载中间计算结果例如 Java 的long、C 的long long位运算Bit Manipulation递归解法解法四利用右移 2 位实现「除以 4」、左移 1 位实现「乘以 2」从而完成对搜索空间的缩放牛顿迭代法Newtons Method一种迭代数值技术收敛速度极快是解法五的理论基石。解法一暴力枚举Brute Force思路平方根就是满足i * i x的最大整数i。因此可以从1开始逐个检查每个整数直到某个整数的平方超过x此时上一个整数就是答案。算法步骤处理边界情况若x 0直接返回0初始化res 1用于记录潜在答案从1遍历到x对每个整数i检查i * i x是否成立若i * i x返回上一个有效结果res否则更新res i并继续遍历循环结束后返回res。复杂度时间复杂度$O(\sqrt{n})$——注意循环最多跑到 $\lfloor \sqrt{x} \rfloor$ 就返回而非x空间复杂度$O(1)$。该解法在x很大例如接近 $2^{31} - 1$时会超时仅作为思路铺垫实际提交需采用更高效的方案。解法二内建函数In-Built Function思路大多数编程语言都提供了内建的平方根函数底层通常使用牛顿迭代法或类似的优化数学算法实现。直接调用内建函数后对结果截断取整即可得到整数平方根。算法步骤调用语言内建的平方根函数计算x的浮点平方根将结果转换为整数截断小数部分返回该整数。各语言实现要点Pythonint(sqrt(x))注意先from math import sqrtJava / C#(int) Math.sqrt(x)/(int) Math.Sqrt(x)浮点转整型时自动截断JavaScriptMath.floor(Math.sqrt(x))使用floor显式向下取整Goint(math.Sqrt(float64(x)))需先转换为float64Rust(x as f64).sqrt() as i32。复杂度时间复杂度$O(1)$空间复杂度$O(1)$。注意虽然内建函数在普通场景下是 $O(1)$但本题要求不得使用内建指数/开方函数因此该解法仅用于理解思路正式提交应以解法三、五为准。解法三二分查找Binary Search——推荐解法思路整数的平方是单调递增的$0^2 1^2 2^2 \dots$满足二分查找的单调性前提。我们要找的是满足m * m x的最大m搜索空间为[0, x]每次根据中间值平方与x的大小关系收缩区间。算法步骤初始化左边界l 0、右边界r x、结果变量res 0当l r时循环计算中间值m l (r - l) / 2用减法代替加法进一步规避l r的溢出风险若m * m x答案必然更小令r m - 1若m * m xm是合法候选存入res继续向右寻找更大的值令l m 1若m * m x恰好找到精确平方根直接返回m循环结束返回res。各语言实现要点以文档中的 Python 实现为例class Solution: def mySqrt(self, x: int) - int: l, r 0, x res 0 while l r: m l (r - l) // 2 if m * m x: r m - 1 elif m * m x: l m 1 res m else: return m return res在 Java / C / Go / Rust 等强类型语言中m * m必须显式转换为 64 位类型再比较例如 Java 的(long) m * m、C 的(long long) m * m、Rust 的m as i64 * m as i64。Python 的整数无精度上限无需处理。仓库源码佐证仓库内多份提交均采用二分查找思路可以作为对照学习python/0069-sqrtx.py 采用mid * mid三分支二分循环退出后返回r此时r恰好是最后一个满足r * r x的值java/0069-sqrtx.java 维护probableAns变量记录候选答案仅当mid * mid x时才更新并右移左边界最终返回最后一次合法候选csharp/0069-sqrtx.cs 采用left right循环结束时返回left - 1c/0069-sqrtx.c 使用long int m承载中间值避免溢出javascript/0069-sqrtx.js 用 1完成除以 2并在循环内直接判断mid * mid x (mid 1) * (mid 1) x提前返回。各实现的循环退出条件与返回值略有差异但本质都是「寻找满足平方不超过x的最大整数」。复杂度时间复杂度$O(\log n)$空间复杂度$O(1)$。解法四位运算递归Recursion思路利用一个简洁的数学恒等式$$\sqrt{x} 2 \cdot \sqrt{x / 4}$$将x右移 2 位等价于除以 4得到更小的子问题递归求出sqrt(x / 4)后左移 1 位等价于乘以 2还原尺度最后检查结果加 1 是否仍合法从而确定精确的整数平方根。算法步骤基准情形若x 2直接返回x因为 $\sqrt{0} 0$、$\sqrt{1} 1$递归计算下界l mySqrt(x 2) 1计算候选值r l 1若r * r x返回l否则返回r。Python 实现class Solution: def mySqrt(self, x: int) - int: if x 2: return x l self.mySqrt(x 2) 1 r l 1 return l if r ** 2 x else r在 Kotlin 中对应写法为mySqrt(x shr 2) shl 1Java / C# / C 则为mySqrt(x 2) 1。各语言的位运算符语义一致 2除以 4 1乘以 2。复杂度时间复杂度$O(\log n)$——每层递归输入缩小为原来的 1/4空间复杂度$O(\log n)$——来自递归调用栈的深度。解法五牛顿迭代法Newtons Method思路牛顿迭代法是求解方程根的经典数值方法。为求 $\sqrt{x}$等价于求函数 $f(r) r^2 - x$ 的根。牛顿迭代公式给出更新规则$$r_{new} \frac{r x / r}{2}$$从初始猜测r x出发反复应用该公式直到r * r x即完成收敛此时r就是整数平方根。从 articles/sqrtx.md 的公式推导可见(r x / r) / 2等价于(r x // r) 1整数除法 右移 1 位这也是各语言实现统一采用右移的原因。算法步骤初始化r x作为初始猜测当r * r x时更新r (r x / r) / 2整数除法或等价地右移 1 位循环在r * r x时终止返回r作为整数平方根。Python 实现class Solution: def mySqrt(self, x: int) - int: r x while r * r x: r (r x // r) 1 return r注意 JavaScript 版本需使用Math.floor(x / r)保证整数除法语义Java / C# 中r声明为long防止平方溢出Kotlin 中x / r在Long类型下自动为整数除法。复杂度时间复杂度$O(\log n)$——牛顿迭代呈二次收敛迭代次数极少空间复杂度$O(1)$。从仓库源码看kotlin/0069-sqrtx.kt 在同一文件中同时给出了二分查找与牛顿迭代两份实现后者以while (i x / i)作为循环条件写法更紧凑可作为两种解法的对照参考。常见陷阱平方运算的整数溢出在二分查找中计算m * m时若m较大32 位整数下约 46340 的平方即接近溢出上限结果可能溢出 32 位整型导致错误比较。务必在乘法前转换为 64 位类型Java 使用(long) m * mC 使用(long long) m * mRust 使用m as i64 * m as i64Go 使用int64(m) * int64(m)。这一点在文档的 Pitfalls 章节和仓库各语言提交中均有体现——例如 cpp/0069-sqrtx.cpp 全程使用long long变量。二分查找中的边界Off-by-One错误一个隐蔽的错误是当m * m x时直接返回m而不再向右搜索。正确做法是把m记录为候选答案并继续向右扩展l m 1因为可能存在更大的合法值。循环结束后返回最后一次记录的候选结果。文档给出的二分模板解法三以及 java/0069-sqrtx.java 的probableAns模式都体现了这一要点。五种解法对比与选型建议解法核心技巧时间复杂度空间复杂度适用场景暴力枚举线性扫描$O(\sqrt{n})$$O(1)$仅用于理解问题定义内建函数语言库函数$O(1)$$O(1)$工程场景无禁用手限制二分查找单调性 分治$O(\log n)$$O(1)$面试/竞赛首选稳定可靠位运算递归数学恒等式 移位$O(\log n)$$O(\log n)$考察位运算与递归技巧牛顿迭代数值分析$O(\log n)$$O(1)$收敛最快体现数学功底从仓库的提交分布看见 README.md 中的完成度表格C、C、C#、Java、JavaScript、Kotlin、Python 均提供了本题的可运行实现其中二分查找是各语言提交的主流方案说明它是该题最具普适性与工程价值的答案。建议读者重点掌握解法三并理解解法五的迭代原理即可完整覆盖该题的考察要点。延伸阅读二分查找的更多变体可参考仓库文章 articles/binary-search.md位运算相关的另一经典题可参考 articles/sum-of-two-integers.md若希望查看本文五种解法的完整多语言代码请直接阅读 articles/sqrtx.md 原文并按需对照仓库内各语言的 0069-sqrtx 实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考