作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
输入格式
- x：一个非负整数。
输出格式
- 返回整数部分的平方根。
示例
示例 1
输入: x = 4 输出: 2
示例 2
输入: x = 8 输出: 2 解释: 8 的平方根是 2.82842..., 因为返回类型是整数，小数部分将被舍去。
方法一：二分查找
解题步骤
- 设置边界：设置
left为 0，right为x。 - 迭代查找：在
left和right之间使用二分查找来确定平方根。 - 检查中点平方：计算中点的平方，与
x比较来调整left或right。
完整的规范代码
def mySqrt(x): """ 使用二分查找计算平方根 :param x: int, 输入的非负整数 :return: int, 平方根的整数部分 """ left, right = 0, x while left <= right: mid = (left + right) // 2 if mid * mid <= x < (mid + 1) * (mid + 1): return mid elif mid * mid < x: left = mid + 1 else: right = mid - 1 # 示例调用 print(mySqrt(4)) # 输出: 2 print(mySqrt(8)) # 输出: 2
算法分析
- 时间复杂度：(O(\log n))，其中
n是输入大小x，二分查找的时间复杂度。 - 空间复杂度：(O(1))，只使用了固定的几个变量。
方法二：牛顿迭代法
解题步骤
完整的规范代码
def mySqrt(x): """ 使用牛顿迭代法计算平方根 :param x: int, 输入的非负整数 :return: int, 平方根的整数部分 """ if x < 2: return x x0 = x x1 = (x0 + x // x0) // 2 while x1 < x0: x0 = x1 x1 = (x0 + x // x0) // 2 return x0 # 示例调用 print(mySqrt(4)) # 输出: 2 print(mySqrt(8)) # 输出: 2
算法分析
- 时间复杂度：(O(log n))，牛顿迭代法通常具有很快的收敛速度。
- 空间复杂度：(O(1))，使用了常数个额外空间。
方法三：内置函数法
解题步骤
- 直接计算：使用 Python 的内置函数
math.sqrt()计算平方根。 - 结果转换：将得到的浮点数结果转换为整数。
完整的规范代码
import math def mySqrt(x): """ 使用内置函数计算平方根 :param x: int, 输入的非负整数 :return: int, 平方根的整数部分 """ return int(math.sqrt(x)) # 示例调用 print(mySqrt(4)) # 输出: 2 print(mySqrt(8)) # 输出: 2
算法分析
- 时间复杂度：(O(1))，内置函数通常优化良好，执行速度快。
- 空间复杂度：(O(1))，不需要额外空间。
方法四：暴力法
解题步骤
- 线性搜索：从 0 开始逐一计算平方，直到平方大于
x。 - 返回结果：返回最后一个平方不超过
x的数。
完整的规范代码
def mySqrt(x): """ 使用暴力法计算平方根 :param x: int, 输入的非负整数 :return: int, 平方根的整数部分 """ ans = 0 while (ans + 1) * (ans + 1) <= x: ans += 1 return ans # 示例调用 print(mySqrt(4)) # 输出: 2 print(mySqrt(8)) # 输出: 2
算法分析
- 时间复杂度：(O(sqrt{n}))，需要计算直到
x的平方根。 - 空间复杂度：(O(1))，使用固定空间。
方法五：位运算法
解题步骤
- 位移操作：通过位操作逐步构建结果的每一位，检查平方后是否小于等于
x。 - 迭代构建结果：从最高位开始尝试，逐步向下调整。
完整的规范代码
def mySqrt(x): """ 使用位运算法计算平方根 :param x: int, 输入的非负整数 :return: int, 平方根的整数部分 """ ans = 0 bit = 1 << 15 # 从高位开始尝试 while bit > 0: ans |= bit if ans * ans > x: ans ^= bit # 如果尝试结果过大，撤销这一位 bit >>= 1 return ans # 示例调用 print(mySqrt(4)) # 输出: 2 print(mySqrt(8)) # 输出: 2
算法分析
- 时间复杂度：(O(log n))，位运算的复杂度为常数次迭代。
- 空间复杂度：(O(1))，不需要额外空间。
不同算法的优劣势对比
| 特征 | 方法一：二分查找 | 方法二：牛顿迭代法 | 方法三：内置函数法 | 方法四：暴力法 | 方法五：位运算法 |
| 时间复杂度 | (O(log n)) | (O(log n)) | (O(1)) | (O(sqrt{n})) | (O(log n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |
| 优势 | 稳定且高效 | 收敛速度快，适用于大数 | 实现简单，运行快速 | 直观易懂 | 不使用乘法和除法，节省资源 |
| 劣势 | 需要处理边界条件 | 初始值依赖较大 | 受内置函数性能限制 | 时间成本较高 | 代码相对复杂，需要位操作知识 |
应用示例
图形处理软件：在处理图形和游戏开发中，经常需要计算对象的大小或者距离，这时候求平方根是常见的需求。例如，计算点到原点的距离，确定对象是否在视野内等。不同的平方根计算方法可以根据性能需求和精确度要求选择。例如，位运算法因为其高效性，非常适合嵌入式系统或游戏开发中，牛顿迭代法则适用于需要高精度计算的科学计算软件。
欢迎关注微信公众号 数据分析螺丝钉
