LeetCode-69-x 的平方根

算法刷题>LeetCode>面试经典150
2.6k words

题目描述

给你一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。不得使用任何内置指数函数和算符，例如 pow(x, 0.5) 或 x ** 0.5。

示例 1：

1
2
输入：x = 4
输出：2

示例 2：

1
2
3
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842...，由于返回类型是整数，小数部分将被舍去。

约束：0 <= x <= 2^31 - 1

解题思路

  • 关键洞见：若记答案为 r = ⌊√x⌋，则有 r^2 <= x < (r+1)^2。因此可以在整数域上使用单调性判定。
  • 方法一（二分查找，详解）：利用单调性在整数区间上二分定位最大 r 使得 r^2 <= x。
  • 方法二（牛顿迭代）：迭代公式 r_{k+1} = (r_k + x / r_k) / 2 收敛很快，取整数部分即可。

二分法详解（不变量、边界与正确性）

  1. 区间定义：使用左闭右闭区间 [left, right]，含义为“答案 r 一定在该区间内”。
  2. 初始化：left = 0，right = x（也可用更紧上界 x / 2 + 1，当 x >= 2 时必成立）。
  3. 不变量：每轮迭代后，r 仍在 [left, right]，且区间严格收缩。
  4. 中点计算：mid = left + ((right - left) >> 1)，避免 left + right 直接相加导致溢出。
  5. 比较与缩小区间：
    • 若 (long)mid * mid < x，说明 mid 偏小，目标在右侧，更新 left = mid + 1。
    • 若 (long)mid * mid > x，说明 mid 偏大，目标在左侧，更新 right = mid - 1。
    • 若相等，直接返回 mid。
  6. 终止与返回：循环以 left > right 终止，此时必有 right^2 <= x < left^2，因此返回 right 即为 ⌊√x⌋。
  7. 溢出处理：比较平方前将 mid 提升为 long 再相乘，避免 int 乘法溢出导致的错误判定。
  8. 特殊值：x ∈ {0,1} 时流程自然成立；如需微优化可在开头直接返回 x。

二分的本质：在单调布尔函数上找“边界”

把问题抽象为布尔谓词 P(m): m^2 <= x。显然 P(m) 关于 m 是单调的：当 m 增大到超过 ⌊√x⌋ 后，P(m) 从真变假。

  • 目标就是找到“真到假”的分界点：最大的 m 使 P(m) 为真。
  • 这正是二分查找在单调布尔数组上的“上界”问题（max-true）。

因此，模板可表述为：在 [0, x] 上找最大 m 使 P(m) 为真；当循环结束，right 指向 max-true，left 指向 min-false。

形式化不变量与正确性（为什么返回 right）

  • 循环保持：I: right 始终满足 P(right)，left 始终不满足 P(left-1)（或说 left 是第一个可能满足的位置）。
  • 当 P(mid) 为真时，mid 及其左侧都为真，最大真值不在 mid 左边，故令 left = mid + 1 不会丢失 max-true。
  • 当 P(mid) 为假时，mid 及其右侧都为假，最大真值在 mid 左边，故令 right = mid - 1 保留所有可能答案。
  • 终止条件 left = right + 1，结合不变量推出：right 为 max-true，left 为 min-false，结论即 right^2 <= x < left^2。

等价谓词与比较技巧（避免乘法溢出）

  • 本文实现用 (long)mid * mid 安全比较。
  • 另一种常见写法是用除法比较：mid <= x / mid 等价于 mid * mid <= x，可避免乘法溢出（但需要注意 x / mid 的整除性质以及 mid != 0）。

常见陷阱与反例

  1. 误返回 left：循环结束后 left 指向第一个使 P(left) 为假的位置，返回它会比正确答案大 1。
  2. 右边界更新错误：在左闭右闭区间中，P(mid) 为假时必须 right = mid - 1，若写成 right = mid 会导致死循环或区间不收缩。
  3. 中点取值与循环条件不匹配：左闭右闭应配合 while (left <= right)；若误用 left < right 可能漏解或死循环。

执行示例（x = 8）

1
2
3
4
5
6
7
8
初始：left = 0, right = 8

第一轮：mid = 4, 4^2 = 16 > 8 → right = 3
第二轮：mid = 1, 1^2 = 1  < 8 → left = 2
第三轮：mid = 2, 2^2 = 4  < 8 → left = 3
第四轮：mid = 3, 3^2 = 9  > 8 → right = 2

结束：left = 3, right = 2（left > right）→ 返回 right = 2

代码实现

解法一：二分查找（你的实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int mySqrt(int x) {
        int mid;
        int left = 0, right = x;
        while(left <= right){
            mid = left +((right - left) >> 1);
            if ((long)mid * mid < x)
                left = mid + 1;
            else if((long)mid * mid > x)
                right = mid - 1;
            else 
                return mid;
        }
        return right;
    }
}

解法二：牛顿迭代（常数更优）

1
2
3
4
5
6
7
8
9
10
class SolutionNewton {
    public int mySqrt(int x) {
        if (x < 2) return x;
        long r = x; // 用 long 防止中间计算溢出
        while (r * r > x) {
            r = (r + x / r) >> 1; // 等价于 (r + x / r) / 2
        }
        return (int) r;
    }
}

方法比较

方面 二分查找 牛顿迭代
时间复杂度 O(log x) 迭代次数很少，实际常数更优
空间复杂度 O(1) O(1)
实现难度 简单、边界清晰 略高，需注意收敛与溢出
稳定性 边界与正确性易于证明 对初始值不敏感，但要用 long

复杂度分析

  • 二分查找：时间 O(log x)，空间 O(1)。
  • 牛顿迭代：每次迭代为常数开销，通常 5～7 次内收敛到整数根，空间 O(1)。

关键收获

  • 在整数域下通过单调性与不等式界定目标区间，是处理“向下取整”的常见套路。
  • 计算平方时建议使用更宽类型（如 long）以避免溢出带来的比较错误。
  • 牛顿法在需要高效近似开方时非常实用，注意以整数形式收敛并保证向下取整性质。