0492. Construct the Rectangle ============================= 题目信息 -------- :题号: 0492 :难度: Easy :主题: 整数面积、长和宽、因数对、最小差值 :原题: `LeetCode 0492 `_ :重点: ``L * W = area``、必须满足 ``L >= W``、在合法整数因数对中最小化 ``L-W``、返回 ``[L,W]`` 题目重述 -------- 给定正整数 ``area``,寻找正整数长度 ``L`` 和宽度 ``W``,使矩形面积满足 ``L * W = area``,并且 ``L >= W``。在所有合法因数对中,选择 ``L - W`` 最小的一对,返回 ``[L, W]``。 ``area`` 位于 ``[1, 10^7]``。答案保证存在且唯一。长度和宽度都必须是正整数,不能使用近似值或非整数边长。 自建示例 -------- 存在接近平方的因数对: .. code-block:: text 输入:area = 30 输出:[6,5] 解释:30 的合法因数对包括 [30,1]、[15,2]、[10,3]、[6,5],最后一对的长宽差最小。 面积为质数: .. code-block:: text 输入:area = 13 输出:[13,1] 解释:13 只有因数 1 和 13,因此这是唯一合法矩形。 从平方根向下寻找最接近因数 -------------------------- 在因数对 ``L * W = area`` 中,若 ``W`` 越接近平方根,``L = area / W`` 就越接近 ``W``,长宽差越小。因此从 ``floor(sqrt(area))`` 向下枚举宽度,第一次整除时得到的 ``[area / W, W]`` 就是最优答案,同时天然满足 ``L >= W``。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector constructRectangle(int area) { for (int width = static_cast(std::sqrt(area)); width >= 1; --width) { if (area % width == 0) { return {area / width, width}; } } return {area, 1}; } }; 代码分析 -------- 因数对关于平方根对称,离平方根最近的可行宽度使 ``L-W`` 最小;向下枚举保证第一次命中就是该宽度。最多检查 ``sqrt(area)`` 个候选,时间复杂度为 ``O(sqrt(area))``,额外空间复杂度为 ``O(1)``。