construct-the-rectangle

Construct the Rectangle – LeetCode 492

Problem

Description

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

• The area of the rectangular web page you designed must equal to the given target area.

• The width W should not be larger than the length L, which means L >= W.

• The difference between length L and width W should be as small as possible.

Answer

Original

Code

class Solution {
public:
    vector<int> constructRectangle(int area) {
        int start = sqrt(area);
        for(; area % start != 0; --start) {}
        return vector<int>({area / start, start});
    }
};

思路

简单的从平方根处开始搜索。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$2.68\%$

Better

思路

还没看到更好的思路。