问题描述
LeetCode 69. x 的平方根 (opens in a new tab)，难度简单。
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入：x = 4 输出：2
示例 2
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
题解
暴力
解题思路：直接遍历平方 i， 判断 x 是否满足 。主要是注意溢出。
Solution.java
class Solution {
public int mySqrt(int x) {
if (x == 0) return 0;
for (int i = 1; i <= x; ++i) {
if ((long)i * i <= x && x < (long)(i + 1) * (i + 1)) {
return i;
}
}
return 0;
}
}二分法
解题思路：直接看代码吧，思路也很清晰，主要是注意溢出。
Solution.java
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int left = 1, right = x;
while (left <= right) {
int mid = left + (right - left) / 2;
long square = (long) mid * mid; // 防止溢出
if (square == x) {
return mid;
} else if (square < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}