剑指offer-78、求平⽅根
题⽬描述
给定⼀个⾮负整数 x ，计算并返回 x 的平⽅根，即实现 int sqrt(int x) 函数。
正数的平⽅根有两个，只输出其中的正数平⽅根。如果平⽅根不是整数，输出只保留整数的部分，⼩数部分将被舍去。
示例1
输⼊：8
返回值：2
解释：8 的平⽅根是 2.82842…，由于⼩数部分将被舍去，所以返回 2
思路及解答
暴力枚举
从0开始递增，找到最大的i满足i² ≤ x < (i+1)²
java
public class Solution { public int sqrt(int x) { // 处理边界情况 if (x < 0) return -1; // 输入非法 if (x <= 1) return x; // 0和1的平方根是自身 // 从1开始线性查找 int i = 1; while (i <= x / i) { // 使用除法避免溢出 i++; } return i - 1; // i是第一个使i² > x的数，所以平方根是i-1 } }- 时间复杂度：O(√x)，最多需要√x次循环
- 空间复杂度：O(1)，只使用常数空间
二分查找（最优解）
在[0, x]范围内查找平方根，不断缩小区间，直到找到满足条件的最大整数
如果 $m^2$ < n, ⽽且 $（m+1）^2$>n，那么说明 m 是 n 的平⽅根。
java
public class Solution { public int sqrt(int x) { if (x < 0) return -1; if (x <= 1) return x; int left = 1; int right = x / 2; // 优化：平方根不会超过x/2（x≥4时） int result = 0; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 long square = (long) mid * mid; // 使用long防止溢出 if (square == x) { return mid; // 找到精确平方根 } else if (square < x) { result = mid; // 记录当前可能的结果 left = mid + 1; // 向右查找 } else { right = mid - 1; // 向左查找 } } return result; } }- 时间复杂度：O(logn)，每次将搜索范围减半
- 空间复杂度：O(1)
牛顿迭代法
这就属于是使用数学方法了
利用切线逼近平方根，迭代公式：xₙ₊₁ = (xₙ + a/xₙ)/2，其中a是要求平方根的数
java
public class Solution { public int sqrt(int x) { if (x < 0) return -1; if (x == 0) return 0; double guess = x; // 初始猜测值 double epsilon = 1e-6; // 精度要求 // 牛顿迭代 while (Math.abs(guess * guess - x) > epsilon) { guess = (guess + x / guess) / 2.0; } return (int) guess; // 向下取整 } /** * 整数版本：避免浮点数运算 */ public int sqrtInt(int x) { if (x < 0) return -1; if (x <= 1) return x; long r = x; // 使用long防止溢出 // 牛顿迭代的整数版本 while (r * r > x) { r = (r + x / r) / 2; } return (int) r; } }- 时间复杂度：O(log x)，收敛速度极快
- 空间复杂度：O(1)，常数空间
位运算
利用二进制特性逐位确定平方根，最高位开始，逐位尝试将1变为0或保持1
java
public class Solution { public int sqrt(int x) { if (x < 0) return -1; if (x <= 1) return x; int result = 0; int bit = 1 << 15; // 从第16位开始尝试（因为int最大值约21亿，平方根约46340） while (bit > 0) { int temp = result | bit; // 尝试将当前位设为1 if (temp <= x / temp) { // 等价于temp² ≤ x result = temp; // 当前位可以设为1 } bit >>= 1; // 移到下一位 } return result; } }- 时间复杂度：O(log x)，固定32次循环（对于int类型）
- 空间复杂度：O(1)，常数空间
位运算原理解析
为什么从第16位开始？
- int最大值：2³¹-1 ≈ 21亿
- √21亿 ≈ 46340 < 2¹⁶ = 65536
- 所以只需要检查16位即可
执行过程示例（x=8，二进制1000）：
text
初始: result=0, bit=1<<15=32768 bit太大，跳过... 直到bit=4: temp=4, 4²=16 > 8 → 不设置 bit=2: temp=2, 2²=4 ≤ 8 → result=2 bit=1: temp=3, 3²=9 > 8 → 不设置 返回: result=2