实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
采用二分法,但是有越界的风险,可以用long型,或者直接写死(代码用的这种方式)。。
public int mySqrt(int x) { if (x == 0) { return 0; } if (x < 4) { return 1; } // 怕越界,先写死 if (x >= 2147395600) { return 46340; } int st = 0; int end = x; int m = st + ((end - st) >> 1); // 怕越界,先写死 if (m>= 46340 ) { m = 46340; } while (st <= end) { int s = m * m; if (s <= x && (m + 1) * (m + 1) > x) { return m; } if (s > x) { end = m - 1; } else { st = m + 1; } m = st + ((end - st) >> 1); } return 0; }
时间还可以。