二分与排序简单2 种解法
#69x 的平方根
返回非负整数 x 的算术平方根向下取整结果。
#数学#二分查找
原题
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
解题主线
- 答案是满足 mid² <= x 的最大整数，可用二分查找最后一个真值。
解法 1：线性试探
从 0 递增，记录平方仍不超过 x 的最后一个整数。
-
时间复杂度： O(√x)
-
空间复杂度： O(1)
final class Solution {
public int mySqrt(int x) {
// answer 始终是当前已验证平方不超过 x 的最大整数。
int answer = 0;
// 乘法提升为 long，避免接近平方根边界时发生 int 溢出。
while ((long) (answer + 1) * (answer + 1) <= x) answer++;
return answer;
}
}解法 2：二分答案
在 [0, x] 中寻找平方不超过 x 的最右位置。
-
时间复杂度： O(log x)
-
空间复杂度： O(1)
final class Solution {
public int mySqrt(int x) {
int left = 0, right = x, answer = 0;
// 在闭区间中寻找满足 middle² <= x 的最右位置。
while (left <= right) {
int middle = left + (right - left) / 2;
// 可行时记录候选并右移；不可行时左侧才可能仍有答案。
if ((long) middle * middle <= x) {
answer = middle;
left = middle + 1;
} else {
right = middle - 1;
}
}
return answer;
}
}边界与易错点
- mid * mid 可能溢出 int，乘法前必须提升为 long。
- x = 0 时答案也是 0。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q069_sqrtx.java