LeetCode 69. Sqrt(x) 题解

LeetCode 69. Sqrt(x) 题解题目描述给你一个非负整数x计算并返回x的 算术平方根 。由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。示例 1输入x 4 输出2示例 2输入x 8 输出2 解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。解题思路二分查找在 [0, x] 范围内查找最大的整数 mid使得 mid² ≤ x时间复杂度 O(log x)代码实现def mySqrt(x): if x 2: return x left, right 2, x // 2 while left right: mid (left right) // 2 square mid * mid if square x: return mid elif square x: left mid 1 else: right mid - 1 return right复杂度分析时间复杂度O(log x)空间复杂度O(1)牛顿迭代法def mySqrt(x): if x 2: return x x0 x x1 (x0 x / x0) / 2 while abs(x1 - x0) 1e-6: x0 x1 x1 (x0 x / x0) / 2 return int(x1)测试案例# 测试案例 1 assert mySqrt(4) 2 # 测试案例 2 assert mySqrt(8) 2 # 测试案例 3 assert mySqrt(0) 0 # 测试案例 4 assert mySqrt(1) 1 # 测试案例 5 assert mySqrt(16) 4总结本题是二分查找的经典应用。关键点二分查找在有序范围中寻找解处理边界情况牛顿迭代法的应用通过本题可以深入理解二分查找的应用场景。