LeetCode LCR 072. x 的平方根
题目描述
题意分析
对非负整数
x，返回平方根的整数部分，即最大的非负整数k，满足 $k^2\le x$。完全平方数应返回精确的根，其余情况向下取整。随着
k增大，条件 $k^2\le x$ 只会从满足变为不满足，因此可以在整数答案范围内二分，寻找最后一个满足条件的值。题目给出 $0\le x\le 2^{31}-1$，实现还需要避免平方乘法溢出。
解法：二分整数平方根上界
核心思路
[!blue]
初始搜索区间取
[0,x]。零一定满足条件；对整数x >= 1，平方根不超过x，所以这个范围包含答案，x == 0时也直接覆盖唯一答案。对正数中点
mid，判定 $mid^2\le x$ 可以等价改写为mid <= x/mid。整数除法向下取整不会改变这个判断：能放下至少mid个大小为mid的单位，正好意味着平方不超过x。这样不必计算可能超出整数范围的乘积。维护闭区间
[left,right]包含答案，其中left是一个已知可行值。若中点满足条件，答案可能就是它，也可能更大，令left = mid；否则中点及其右侧都过大，令right = mid-1。因为可行分支保留
mid作为左端，中点必须向上取整。只要left < right，就有left < mid <= right，两种更新都能缩小范围。并且left >= 0，进入循环后的中点一定大于零，所以除法不会遇到零分母。Java 用
(left+right+1) >>> 1取上中点：在本题非负 32 位范围内，无符号右移按加和的位模式得到正确结果，不能换成有符号右移。Go 用等价的right-(right-left)/2，既向上取整，又避免先计算right-left+1在 32 位整数上界溢出。
解题步骤
- 设置
left = 0、right = x。- 当左右边界不同，计算上中点并判断
mid <= x/mid。- 可行就把左端移到中点，不可行就把右端移到中点前一位。
- 区间只剩一个整数时返回
left，它就是最大的可行候选。
x == 0时循环不执行；x == 1时唯一需要检查的正数中点为一。完全平方数的根满足带等号的判定，会被保留下来。
代码实现
class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
while (left < right) {
int mid = (left + right + 1) >>> 1;
if (mid <= x / mid) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
func mySqrt(x int) int {
left, right := 0, x
for left < right {
mid := right - (right-left)/2
if mid <= x/mid {
left = mid
} else {
right = mid - 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log(x+1))$，每轮缩小约一半候选，题目范围内最多约 $31$ 轮。
- 空间复杂度：$O(1)$，只维护几个整数下标。
关键点总结
[!green]
- 向下取整的平方根是最后一个平方不超过
x的整数，搜索目标仍是离散边界。left = mid必须配上中点，使两个候选时仍能推进。- 除法判定避免平方溢出；循环不变量同时保证分母为正。
易错点总结
[!yellow]
- 直接用普通整数计算
mid*mid，可能在比较之前就已经溢出。- 使用下中点却仍更新
left = mid，可能卡在两个候选之间。- 不可行时仍保留中点，或可行时把中点排除，都会破坏当前边界含义。
- 只处理正数而漏掉
x == 0，或把完全平方数根上的等号排除。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 367. 有效的完全平方数 | 简单 | 同样比较平方与目标，原题判断是否恰为完全平方，本题返回平方根的整数下界。 |
| 441. 排列硬币 | 简单 | 同样对单调增长的数值表达式二分，原题找满足三角数不超过n的最大层数。 |