0069. Sqrt(x)
=============
题目信息
--------
:题号: 0069. x 的平方根
:难度: Easy
:主题: 数学、二分查找、牛顿迭代、整数边界
:原题: `LeetCode 0069 `_
:重点: 从逐个试探平方根,推导到单调边界二分与整数牛顿迭代
题目重述
--------
给定非负整数 ``x``,返回 ``sqrt(x)`` 向下取整后的整数。不能使用内置指数函数或运算符,
例如 ``pow(x, 0.5)``。
约束为 ``0 <= x <= 2^31 - 1``。返回值 ``r`` 必须满足:
.. code-block:: text
r^2 <= x < (r + 1)^2
自建示例
--------
.. code-block:: text
输入:x = 50
输出:7
``7^2 = 49 <= 50``,而 ``8^2 = 64 > 50``,所以向下取整后得到 ``7``。
.. code-block:: text
输入:x = 2147395600
输出:46340
该输入恰好等于 ``46340^2``,因此返回 ``46340``。
.. code-block:: text
输入:x = 8
输出:2
``sqrt(8)`` 位于 ``2`` 与 ``3`` 之间,向下取整后得到 ``2``。
C++ 实现
--------
.. code-block:: cpp
class Solution {
private:
int linearSearch(int x) {
if (x < 2) {
return x;
}
int answer = 1;
for (int candidate = 2;
candidate <= x / candidate;
++candidate) {
answer = candidate;
}
return answer;
}
int binaryLastTrue(int x) {
if (x < 2) {
return x;
}
int left = 1;
int right = x / 2 + 1;
int answer = 1;
while (left <= right) {
const int middle = left + (right - left) / 2;
if (middle <= x / middle) {
answer = middle;
left = middle + 1;
} else {
right = middle - 1;
}
}
return answer;
}
int newtonIteration(int x) {
if (x < 2) {
return x;
}
long long estimate = x;
while (estimate > x / estimate) {
estimate = (estimate + x / estimate) / 2;
}
return static_cast(estimate);
}
public:
int mySqrt(int x) {
return binaryLastTrue(x);
}
};
题解
----
逐个验证候选值
~~~~~~~~~~~~~~
向下取整平方根不是寻找一个一定满足 ``candidate^2 == x`` 的整数,而是寻找满足
``candidate^2 <= x`` 的最大整数。
``linearSearch`` 从 ``1`` 开始递增候选值。只要当前候选仍合法,就把它记录为答案;第一个不合法值之后的
所有整数平方只会更大,因此无需继续检查。
候选最多增长到 ``sqrt(x)`` 附近,时间复杂度为 ``O(sqrt(x))``。这一步直接对应定义,也揭示了可用于优化的
单调结构。
除法形式的平方判断
~~~~~~~~~~~~~~~~~~
若直接计算 ``candidate * candidate``,乘积可能超过 32 位有符号整数范围。对于正整数 ``candidate``,下面两种
判断等价:
.. code-block:: text
candidate^2 <= x
candidate <= x / candidate
整数除法向下取整。若 ``candidate^2 <= x``,则商至少为 ``candidate``;若平方大于 ``x``,则商必小于
``candidate``。代码因此不需要执行可能溢出的乘法。
最后真值边界
~~~~~~~~~~~~
定义谓词:
.. code-block:: text
valid(candidate) = candidate <= x / candidate
候选值从小到大时,``valid`` 只会从 ``true`` 变为 ``false``。目标就是最后一个使谓词为真的整数,可以使用
二分查找。
当 ``middle`` 合法时,它已经是一个可行答案,同时右侧仍可能存在更大的合法值,因此记录 ``middle``,并令
``left = middle + 1``。当 ``middle`` 非法时,它及其右侧全部非法,因此令 ``right = middle - 1``。
``answer`` 始终保存已经验证过的最大合法候选。循环结束时搜索区间为空,所有更大的候选都已排除,
``answer`` 就是向下取整平方根。
搜索区间
~~~~~~~~
``x`` 为 ``0`` 或 ``1`` 时,平方根就是自身,代码直接返回。
对于 ``x >= 2``,平方根不会超过 ``x / 2 + 1``,因此二分区间可以初始化为:
.. code-block:: text
[1, x / 2 + 1]
即使使用更宽的 ``[1, x]``,结果仍正确;较紧的右边界只减少常数级搜索范围。
边界演化
~~~~~~~~
以 ``x = 27`` 为例:
.. list-table::
:header-rows: 1
* - 区间
- 中点
- 判断
- 更新
* - ``[1, 14]``
- 7
- ``7 > 27 / 7``
- ``right = 6``
* - ``[1, 6]``
- 3
- ``3 <= 27 / 3``
- 记录 3,``left = 4``
* - ``[4, 6]``
- 5
- ``5 <= 27 / 5``
- 记录 5,``left = 6``
* - ``[6, 6]``
- 6
- ``6 > 27 / 6``
- ``right = 5``
搜索结束后,最后一个合法候选为 ``5``。
整数牛顿迭代
~~~~~~~~~~~~
方程 ``r^2 = x`` 的牛顿更新式为:
.. code-block:: text
next = (estimate + x / estimate) / 2
``newtonIteration`` 从 ``estimate = x`` 开始。只要 ``estimate > x / estimate``,当前估计的平方就大于 ``x``,
仍需继续缩小。
在该条件下,``x / estimate < estimate``,所以新的整数估计严格小于旧值。实数算术中的两项平均值不会低于
``sqrt(x)``;向下取整后也不会越过目标整数的下界。估计值因此从上方单调下降,最终停在
``floor(sqrt(x))``。
停止时满足 ``estimate <= x / estimate``,即 ``estimate^2 <= x``。若它还能再增加 1,牛顿序列就不会从上方
越过该更大合法整数,因此当前值正是最大合法整数。
方法关系
~~~~~~~~
线性试探按顺序检查所有候选值,直接建立“最后一个合法整数”的目标。二分查找利用合法性随候选值单调变化,
跳过大部分候选。牛顿迭代不再维护显式搜索区间,而是利用方程结构快速缩小过大的估计。
公开入口选择 ``binaryLastTrue``。它的边界不变量明确,只使用整数除法,并能稳定处理 ``2^31 - 1`` 附近的输入。
复杂度分析
~~~~~~~~~~
设输入为 ``x``:
* 线性试探时间 ``O(sqrt(x))``,额外空间 ``O(1)``;
* 二分查找时间 ``O(log x)``,额外空间 ``O(1)``;
* 牛顿迭代使用常数空间,迭代轮数不超过 ``O(log x)``,实际通常更少。
边界处理
~~~~~~~~
* ``x = 0`` 或 ``x = 1`` 时直接返回自身;
* 完全平方数会被识别为最后一个合法候选;
* 非完全平方数返回小于真实平方根的最大整数;
* 平方比较使用 ``candidate <= x / candidate``,避免 32 位乘法溢出;
* 牛顿法只在 ``x >= 2`` 时执行,因此除数 ``estimate`` 始终为正。