本文主要是介绍leetcode题目69:x的平方根【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, xwhile left <= right:mid = (left + right) // 2if mid * mid <= x < (mid + 1) * (mid + 1):return midelif mid * mid < x:left = mid + 1else: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 xx0 = xx1 = (x0 + x // x0) // 2while x1 < x0:x0 = x1x1 = (x0 + x // x0) // 2return x0# 示例调用
print(mySqrt(4)) # 输出: 2
print(mySqrt(8)) # 输出: 2
算法分析
- 时间复杂度:(O(log n)),牛顿迭代法通常具有很快的收敛速度。
- 空间复杂度:(O(1)),使用了常数个额外空间。
方法三:内置函数法
解题步骤
- 直接计算:使用 Python 的内置函数
math.sqrt()
计算平方根。 - 结果转换:将得到的浮点数结果转换为整数。
完整的规范代码
import mathdef 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 = 0while (ans + 1) * (ans + 1) <= x:ans += 1return 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 = 0bit = 1 << 15 # 从高位开始尝试while bit > 0:ans |= bitif ans * ans > x:ans ^= bit # 如果尝试结果过大,撤销这一位bit >>= 1return 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)) |
优势 | 稳定且高效 | 收敛速度快,适用于大数 | 实现简单,运行快速 | 直观易懂 | 不使用乘法和除法,节省资源 |
劣势 | 需要处理边界条件 | 初始值依赖较大 | 受内置函数性能限制 | 时间成本较高 | 代码相对复杂,需要位操作知识 |
应用示例
图形处理软件:在处理图形和游戏开发中,经常需要计算对象的大小或者距离,这时候求平方根是常见的需求。例如,计算点到原点的距离,确定对象是否在视野内等。不同的平方根计算方法可以根据性能需求和精确度要求选择。例如,位运算法因为其高效性,非常适合嵌入式系统或游戏开发中,牛顿迭代法则适用于需要高精度计算的科学计算软件。
这篇关于leetcode题目69:x的平方根【python】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!