解法一 袖珍计算器法

思路:将开方运算转化为其他函数运算 注意点:由于对数与指数运算都是浮点型运算，因此存在精度缺失的问题，因此在得到结果的整数部分 ans 后，我们应当找出 ans 与 ans+1 中哪一个是真正的答案。

class Solution { /** *袖珍计算器法，使用对数、指数运算代替开方运算,时间复杂度O(1),空间复杂度O(1) */ public int mySqrt(int x) { if(x == 0) return 0;//对数真数不能为0 int ans = (int)Math.exp(0.5 * Math.log(x)); //注意浮点运算会出现精度缺失，转化为整数时会出现“少1”的情况，因此要做判断 return (long)(ans+1)*(ans+1) <= x ? ans+1 : ans; } }

解法二 二分查找法

一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。

对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1，也就是说 h = 2，l = 3，因此最后的返回值应该为 h 而不是 l。

class Solution { public int mySqrt(int x) { if (x <= 1) return x; int left = 1, right = x; while (left <= right) { int mid = left + (right - left)/2; int sqrt = x/mid; if (sqrt > mid) { left = mid + 1; } else if (sqrt < mid) { right = mid - 1; } else { return mid; } } return right; } } class Solution { public int mySqrt(int x) { int lo = 1, hi = x; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if ((long)mid * mid > x) { hi = mid - 1; } else if ((long)mid * mid < x) { lo = mid + 1; } else { return mid; } } return hi; } }

解法三 牛顿迭代法

要求x的开方则就是求$f(t)=t^2-x$的正根，可以将f(t)在某个初始值进行泰勒展开，取前两项作为近似函数$g(t)$近似$f(t)$,由近似函数$g(t)$计算得到的根作为初始值再次近似$f(x)$这样近似函数的根就会越来越接近真实值，我们只需要设置一个可以接受的偏差e,当近似值小于这个偏差时就得到了结果。 这篇文章讲的很清楚:传送门

class Solution { public int mySqrt(int x) { if(x=0)return 0; double c = (double)x; double e = 1e-15; double t = c;//设置初始值 while(Math.abs(t - c/t)> e * t) t = (t + c/t)/2; return (int)t; } }