剑指offer-78、求平⽅根

题⽬描述给定⼀个⾮负整数 x 计算并返回 x 的平⽅根即实现 int sqrt(int x) 函数。正数的平⽅根有两个只输出其中的正数平⽅根。如果平⽅根不是整数输出只保留整数的部分⼩数部分将被舍去。示例1输⼊8返回值2解释8 的平⽅根是 2.82842…由于⼩数部分将被舍去所以返回 2思路及解答暴力枚举从0开始递增找到最大的i满足i² ≤ x (i1)²javapublic 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, ⽽且 $m1^2$n那么说明 m 是 n 的平⽅根。javapublic 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/2x≥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是要求平方根的数javapublic 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或保持1javapublic 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位即可执行过程示例x8二进制1000text初始: result0, bit11532768 bit太大跳过... 直到bit4: temp4, 4²16 8 → 不设置 bit2: temp2, 2²4 ≤ 8 → result2 bit1: temp3, 3²9 8 → 不设置 返回: result2