LeetCode LCR 072. x 的平方根

约 8 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数学 二分查找 LCR
目录

题目描述

✅ LCR 072. x 的平方根

题意分析

给一个非负整数 x，返回它算术平方根的整数部分，小数部分一律舍去。也就是求最大的非负整数 k，使得 $k^2 \le x$。

「向下取整」这个要求把问题从「求实数根」变成了「在整数上找边界」：候选答案是 $0, 1, 2, \dots$ 这个有序序列，而「$k^2 \le x$」这个性质随着 k 增大只会从真变假一次——小的 k 全部满足，大的 k 全部不满足。要找的正是最后一个满足条件的 k。这是典型的「二分答案」形态：二分的对象不是给定数组的下标，而是答案本身的取值域。

题目通常还会禁止使用内置的开方函数，这一条正是把考点锁在「如何自己逼近」上。

约束是 x 不超过 $2^{31} - 1$。这条约束在实现上有决定性影响：mid * mid 在 mid 稍大时就会超出 32 位有符号整数，直接比较必然溢出。

边界上要注意：x = 0 时答案是 0，x = 1 时答案是 1，这两个最小规模必须能正确返回；x 为完全平方数时答案恰好是根本身，不能被舍成小一位。

解法：二分查找判定答案

核心思路

暴力做法是从 0 开始逐个试，累加到第一个平方超过 x 的数就停。$O(\sqrt{x})$，在 $x$ 接近 $2^{31}$ 时约 4.6 万次循环，能过但没体现出对单调性的利用。

瓶颈在于线性试探每次只排除一个候选，而「$k^2 \le x$」这个性质是单调的：一旦发现某个 k 的平方已经超过 x，比它大的所有 k 都不必再试；反之若某个 k 满足，比它小的都不必再试。每次比较本可以砍掉一半候选。

于是把答案的取值域 [0, x] 当作搜索区间做二分。取 x 作为上界是安全的：对任意非负整数 x，$\sqrt{x} \le x$ 恒成立（x = 0 和 x = 1 时取等）。

判定条件是 mid * mid <= x，但因为溢出风险，实际写成等价的 mid <= x / mid（整数除法）。这个变形是安全的：当 mid <= x / mid 成立时，由整数除法的性质有 $mid \cdot mid \le x$；当它不成立时，$mid > x / mid$ 意味着 $mid \cdot mid > x$。两边同时把一次乘法换成一次除法，值域就再也不会溢出。

维持的不变量是：答案始终落在 [left, right] 内；left 及其左侧的所有候选都满足 $k^2 \le x$，right 右侧的所有候选都不满足。这是「找最后一个为真」的右边界二分：判定为真时保留 mid（left = mid），为假时排除（right = mid - 1）。

由于 left = mid 不会让区间缩短，中点必须向上取整（mid = (left + right + 1) / 2），否则在区间只剩两个元素时 mid 恒等于 left，赋值后区间原地踏步，陷入死循环。取整方向与收缩方式的这种配对关系，是右边界二分的固定搭配。

解题步骤

  • 令 left = 0、right = x，把整个可能的答案域纳入搜索范围。上界取 x 而不是 x / 2 之类的估计值，是为了让 x = 1 这种小规模也被正确覆盖。
  • 循环条件写 left < right，收缩到唯一候选时退出。x = 0 时循环一次都不进，直接返回 0，边界天然成立。
  • 中点用 (left + right + 1) >>> 1 向上取整。这个 +1 是与下面 left = mid 配套的：右边界二分若用向下取整，两元素区间会死循环。无符号右移同时防止了 left + right + 1 在 x 接近 $2^{31}$ 时溢出成负数。
  • 判定用 mid <= x / mid 而不是 mid * mid <= x。后者在 mid 超过 46341 时就会溢出 32 位整数，得到负值并被误判为满足条件。除法形式与它数学等价却永不溢出。
  • 判定为真时 left = mid：mid 自身满足 $mid^2 \le x$，它有资格当答案，必须保留；把它排除会丢掉完全平方数的正确解。
  • 判定为假时 right = mid - 1：mid 的平方已经超了，它和它右边的候选全部出局。
  • 退出循环时 left == right，返回 left。因为不变量保证了它是最后一个满足条件的候选，即整数平方根。

以 x = 8 走一遍：初始 left = 0、right = 8。第一轮 mid = (0 + 8 + 1) / 2 = 4，判定 4 <= 8 / 4 = 2 为假，说明 $4^2 = 16 > 8$，right = 3。第二轮 mid = (0 + 3 + 1) / 2 = 2，判定 2 <= 8 / 2 = 4 为真，说明 $2^2 = 4 \le 8$，保留，left = 2。第三轮 mid = (2 + 3 + 1) / 2 = 3，判定 3 <= 8 / 3 = 2 为假，说明 $3^2 = 9 > 8$，right = 2。此时 left == right == 2，返回 2——正是 $\sqrt{8} \approx 2.83$ 向下取整的结果。注意第三轮若中点向下取整会得到 2，与 left 相同且 left = mid 后区间不变，正是那个必须靠 +1 规避的死循环。

代码实现

class Solution {
    public int mySqrt(int x) {
        int left = 0, 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 := left + (right-left+1)>>1
        if mid <= x/mid {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

复杂度分析

  • 时间复杂度：$O(\log x)$，搜索区间长度为 $x$ 且每轮至少减半，因此最多约 31 轮循环，每轮只做一次整数除法与比较。
  • 空间复杂度：$O(1)$，只用了 left、right、mid 三个整数变量，没有任何辅助结构或递归栈。

关键点总结

  • 「求满足某单调性质的最大整数」是二分答案的标准信号。二分的对象是答案的值域而不是某个数组的下标，识别出这一点就能把一大类「最小化最大值」「最大化最小值」的题纳入同一套模板。
  • 右边界二分（找最后一个为真）必须用向上取整的中点，配 left = mid 与 right = mid - 1；左边界二分（找第一个为真）用向下取整，配 right = mid 与 left = mid + 1。取整方向与收缩方式必须成对出现，混用必死循环。
  • 判定式里出现乘法且值域接近类型上限时，优先改写成除法或提前用更宽的类型。a * a <= x 改成 a <= x / a 是最省事的等价变形，不需要 long 也不需要浮点。
  • 搜索上界要选一个可证明的安全值。这里用 x 而不是精细估计，是因为多几轮二分完全不影响复杂度，而估计失误会直接丢解。
  • 二分的正确性完全依赖「判定性质随候选单调变化」。写代码前先确认「小的全真、大的全假」，再套模板，顺序不能反。
  • 面试视角：面试官通常会追问溢出如何处理，这是本题最核心的得分点。主动说明「改用 mid <= x / mid 规避乘法溢出」，比写完再被指出要好得多；也可以答「用 long 存 mid * mid」，但要说清 Java 中 int 相乘会先溢出再赋值，必须写成 (long) mid * mid。
  • 面试视角：常见追问是「怎么求到小数点后若干位」或「有没有更快的方法」。前者答把二分搬到实数域、以精度 eps 为终止条件；后者答牛顿迭代法 $x_{n+1} = (x_n + a / x_n) / 2$，收敛速度是平方级，能报出这个名字并写出迭代式通常就足够了。

易错点总结

  • 错误写法：判定写成 mid * mid <= x。用例 x = 2147395600 → 二分过程中 mid 会取到 46341 以上，mid * mid 溢出 32 位整数变成负数，被误判为满足条件，返回值远大于正确答案 46340。
  • 错误写法：中点用向下取整 (left + right) >>> 1 却仍写 left = mid。用例 x = 8 → 区间收缩到 [2, 3] 时 mid 恒为 2，left = 2 后区间不变，死循环。
  • 错误写法：判定为真时写 left = mid + 1。用例 x = 4 → 正确答案 2 在某轮成为 mid 并被排除，最终返回 1，完全平方数全部会少 1。
  • 错误写法：判定为假时写 right = mid。用例 x = 8 → 区间无法在右侧收缩到位，配合向上取整的中点会在两元素区间反复取到同一个 mid，死循环。
  • 错误写法：right 初始化为 x / 2 而不特判小值。用例 x = 1 → 搜索区间是 [0, 0]，直接返回 0，正确答案是 1。
  • 错误写法：中点写成 (left + right + 1) / 2 且用有符号除法。用例 x = 2147483647 → left + right + 1 溢出成负数，mid 变负，x / mid 得到负值，判定与收缩全部错乱。
  • 错误写法：忘记 x = 0 的情况，直接从 left = 1 开始二分。用例 x = 0 → 区间 [1, 0] 非法，循环不进入却返回 1，正确答案是 0；更糟的实现会在 x / mid 处除以 0 抛异常。
  • 错误写法：用 Math.sqrt 求出浮点根再强转 int。用例 x = 2147395600 → 浮点表示在大数上存在精度误差，可能得到 46339.999… 被截断成 46339，正确答案是 46340；何况题目通常明确禁止内置开方。

相似题目

题目 难度 考察点
69. x 的平方根 简单 与本题同题，可用来对照二分答案与牛顿迭代两条路线
367. 有效的完全平方数 简单 只需判定是否恰好相等，答案从边界值退化成布尔判断
875. 爱吃香蕉的珂珂 中等 判定条件从一次乘除变成一轮 $O(n)$ 的可行性检查
1011. 在 D 天内送达包裹的能力 中等 二分答案配合贪心分段，且下界必须取单件最大值而非 1
410. 分割数组的最大值 困难 最小化最大值的经典形态，判定同样是贪心分段计数
1482. 制作 m 束花所需的最少天数 中等 二分的是天数，判定需扫描数组统计连续段，还要先判无解
35. 搜索插入位置 简单 左边界二分的样板，可对照两套取整方向与收缩规则的配对关系