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

写在前面

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

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

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

---

Tag

【数学】

---

题目来源

69. x 的平方根

---

解题思路

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

• 数学表达式；
• 二分法。

方法一：数学表达式

$$\sqrt{x}=x^{\frac{1}{2}}=(e^{lnx}{)}^{\frac{1}{2}}=e^{\frac{1}{2}lnx}$$

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

需要注意的是由于计算机无法存储高精度的浮点值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x=2147395600 时，$e^{\frac{1}{2}lnx}$ 的计算结果与正确答案 46340 相差 $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;
    }
};
1
2
3
4
5
6
7
8
9
10

复杂度分析

时间复杂度：$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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析

时间复杂度：$O(logx)$。

空间复杂度：$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
1
2
3
4
5
6
7
8
9
10
11

---

写在最后

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

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

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