【面试经典150|算术平方根】

文章目录 写在前面Tag题目来源解题思路方法一：数学表达式方法二：二分法 其他语言python3 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；题目来源：贴上题目的链接，方便大家查找题目并完成练习；题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【数学】

---

题目来源

69. x 的平方根

---

解题思路

有一种朴素的方法可以计算 x 的平方根，就是枚举 1 到 x \sqrt{x} x ​，对一个个数的平方进行验证，时间复杂度为 O ( x ) O(\sqrt{x}) O(x ​)，这里我们就不介绍了。接下来介绍两种时间复杂度更优的方法：

数学表达式；二分法。 方法一：数学表达式

x = x 1 2 = ( e l n x ) 1 2 = e 1 2 l n x \sqrt{x} = x^{\frac{1}{2}} = (e^{lnx})^{\frac{1}{2}}= e^{\frac{1}{2}lnx} x ​=x21​=(elnx)21​=e21​lnx

根据以上公式我们就可以得到 x \sqrt{x} x ​ 的值了。

需要注意的是由于计算机无法存储高精度的浮点值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x=2147395600 时， e 1 2 l n x e^{\frac{1}{2}lnx} e21​lnx 的计算结果与正确答案 46340 相差 1 0 − 11 10^{-11} 10−11，这样对结果取整数部分时，会得到 46339 这个错误的结果。

因此在得到结果的整数部分 res 后，我们应当找出 res 与 res+1 中哪一个是真正的答案。

实现代码

class Solution { public: int mySqrt(int x) { if (x == 0) { return 0; } int res = exp(0.5 * log(x)); return (long long)(res + 1) * (res + 1) <= x ? res + 1 :res; } };

复杂度分析

时间复杂度： O ( 1 ) O(1) O(1)。

空间复杂度： O ( 1 ) O(1) O(1)。

方法二：二分法

我们可以二分枚举答案，从 0 到 x 二分枚举，中点记为 mid，如果 mid * mid <= x，那么 mid 就是可能的答案：

如果 mid * mid < = x，更新 l = mid + 1 并记录 res = mid；如果 mid * mid > x，更新 r = mid - 1；如此二分，直到 l > r；最后返回 res。

实现代码

class Solution { public: int mySqrt(int x) { int l = 0, r = x, res; while (l <= r) { int mid = l + (r - l) / 2; if ((long long)mid * mid <= x) { res = mid; l = mid + 1; } else if ((long long)mid * mid > x){ r = mid - 1; } } return res; } };

复杂度分析

时间复杂度： O ( l o g x ) O(logx) O(logx)。

空间复杂度： O ( 1 ) O(1) O(1)。

其他语言 python3

这里展示的是二分查找的python3代码。

class Solution: def mySqrt(self, x: int) -> int: l, r, ans = 0, x, -1 while l <= r: mid = (l + r) // 2 if mid * mid <= x: ans = mid l = mid + 1 else: r = mid - 1 return ans

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。