x 的平方根
- 标签(题目类型)：数学、二分查找
题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 解释: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
思路及实现
方式一：二分查找
思路
由于平方根函数的性质，我们知道平方根一定位于0和x之间（x为非负整数）。因此，我们可以使用二分查找算法在0到x之间查找平方根。在每次迭代中，我们计算中间值mid的平方，如果它等于x，则mid就是平方根；如果它小于x，则平方根一定在mid的右侧；如果它大于x，则平方根一定在mid的左侧。通过不断缩小查找范围，最终我们可以找到平方根。
代码实现
Java版本
public class Solution { public int mySqrt(int x) { if (x < 2) return x; // 特殊情况处理 long left = 2; // 左边界设为2，因为1的平方根为1，无需查找 long right = x / 2; // 右边界设为x/2，因为平方根不会大于x/2 while (left <= right) { long mid = left + (right - left) / 2; // 防止溢出 long square = mid * mid; if (square == x) { return (int) mid; } else if (square < x) { left = mid + 1; // 平方根在mid右侧 } else { right = mid - 1; // 平方根在mid左侧 } } // 因为我们查找的是小于等于x的最大的平方根，所以返回right return (int) right; } }
说明：
- 使用
long类型进行中间计算，防止整数溢出。- 当
square等于x时直接返回结果。- 如果
square小于x，则平方根一定在mid的右侧，因此更新左边界为mid + 1。- 如果
square大于x，则平方根一定在mid的左侧，因此更新右边界为mid - 1。- 最终返回的是
right，因为在循环结束时，right会指向小于等于x的最大的平方根。
C语言版本
#include <math.h> int mySqrt(int x) { if (x < 2) return x; long left = 2; long right = x / 2; while (left <= right) { long mid = left + (right - left) / 2; long square = mid * mid; if (square == x) { return (int)mid; } else if (square < x) { left = mid + 1; } else { right = mid - 1; } } return (int)right; }
说明：
- 与Java版本类似，C语言版本也使用了二分查找的思想。
- 使用了
long类型进行中间计算以避免溢出。
Python3版本
class Solution: def mySqrt(self, x: int) -> int: if x < 2: return x left = 2 right = 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
说明：
- Python版本同样采用了二分查找的思路。
- 由于Python整数运算不会溢出，这里不需要使用额外的数据类型来避免溢出。
Golang版本
package main import ( "math" ) func mySqrt(x int) int { if x < 2 { return x } left := 2 right := x / 2 for left <= right { mid := left + (right-left)/2 square := mid * mid if square == x { return mid } else if square < x { left = mid + 1 } else { right = mid - 1 } } return right } func main() { // 测试代码 x := 8 result := mySqrt(x) println(result) // 输出应为 2 }
说明：
- Golang版本同样使用了二分查找的思想来计算平方根。
left和right分别表示查找范围的左右边界。- 在循环中，根据中间值
mid的平方与x的比较结果来更新查找范围。- 最终返回
right，它是小于等于x的最大的平方根。
复杂度分析
- 时间复杂度：O(log x)，因为每次迭代都将查找范围减半。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
方式二：牛顿迭代法
思路
牛顿迭代法是一种在实数上近似求解方程的方法。对于平方根的计算，我们可以使用牛顿迭代法的公式, 来不断逼近平方根的值。
牛顿迭代法的公式可以表示为：
xₙ₊₁ = xₙ - f(xₙ) / f’(xₙ)
其中，xₙ是第n次迭代的解， xₙ₊₁是第n+1次迭代的解， f(xₙ)是函数在xₙ处的函数值， f’(xₙ)是函数在xₙ处的导数值。
这个公式用于不断逼近函数的根，直到满足一定的精度要求。
代码实现
Java版本
public class Solution { public int mySqrt(int x) { if (x == 0) return 0; double last = 0, curr = x; while (Math.abs(curr - last) > 0.00001) { last = curr; curr = (curr + x / curr) / 2; } return (int) curr; } }
说明：
- 初始化
last为0，curr为x。- 在循环中，根据牛顿迭代法的公式更新
curr的值。- 当
curr和last的差值小于某个很小的阈值时，认为找到了足够接近的解，跳出循环。- 返回
curr的整数部分作为结果。
C语言版本
#include <math.h> int mySqrt(int x) { if (x == 0) return 0; double last = 0, curr = x; double epsilon = 0.00001; while (fabs(curr - last) > epsilon) { last = curr; curr = (curr + x / curr) / 2; } return (int)curr; }
说明：
- C语言版本与Java版本类似，使用了牛顿迭代法来逼近平方根。
- 使用了
fabs函数来计算浮点数之间的绝对值。
Python3版本
class Solution: def mySqrt(self, x: int) -> int: if x == 0: return 0 last = 0.0 curr = x epsilon = 0.00001 while abs(curr - last) > epsilon: last = curr curr = (curr + x / curr) / 2 return int(curr)
说明：
- Python版本同样使用了牛顿迭代法。
- 使用了
abs函数来计算浮点数之间的绝对值。
Golang版本
package main import ( "math" ) func mySqrt(x int) int { if x == 0 { return 0 } last := 0.0 curr := float64(x) epsilon := 0.00001 for math.Abs(curr-last) > epsilon { last = curr curr = (curr + float64(x)/curr) / 2 } return int(curr) } func main() { // 测试代码 x := 8 result := mySqrt(x) println(result) // 输出应为 2 }
说明：
- Golang版本使用了牛顿迭代法来计算平方根。
epsilon定义了收敛的阈值，当连续两次迭代结果的差值小于这个阈值时，认为找到了足够精确的解。math.Abs函数用于计算浮点数之间的绝对值。
复杂度分析
- 时间复杂度：与选择的阈值
epsilon有关，但通常很快收敛，所以时间复杂度相对较低。 - 空间复杂度：O(1)，只使用了常数级别的额外空间。
总结
| 方法 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 | 其他 |
| 二分查找 | 思路简单，直观易懂 | 可能不是最优解，对于非整数平方根需要额外处理 | O(log x) | O(1) | 适用于整数平方根计算 |
| 牛顿迭代 | 收敛速度快，通常很快能得到近似解 | 需要选择合适的初始值和阈值 | 近似O(1) | O(1) | 适用于需要高精度或浮点数平方根计算 |
相似题目
这些题目都涉及到数学运算和数值计算，与平方根计算有一定的相似性，可以用于加深对数值计算和相关算法的理解。请注意，这里提供的链接是基于假设的，实际链接需要根据具体的在线编程平台（如力扣）进行查找。
