leetcode 492. 构造矩形（Java版，三种解法）

ゝ一世哀愁。 2023-01-18 14:21 62阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/construct-the-rectangle/][https_leetcode-cn.com_problems_construct-the-rectangle]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：O(n^2) 暴力解法 ####

双循环，小优化是：保证宽比长大

public int[] constructRectangle(int area) { 
            int minDif = area;
            int length = 0; // 大
            int width = 0; // 小
            for (int i = 1; i <= area; i++) {  // 大
                for (int j = 1; j <= i; j++) {  // 小
                    if (i * j > area) break;
                    else if (i * j == area) { 
                        if (i - j < minDif) { 
                            minDif = i - j;
                            length = i;
                            width = j;
                        }
                    }
                }
            }
            return new int[]{ length, width};
        }

#### 方法2：O(n)，双指针解法 ####

首先取 area 的根，如果直接可以开的整数，那么就直接输出。  
如果不能直接整开，就需要双指针，一个指大，一个指小不断向两边扩展。

public int[] constructRectangle(int area) { 
            int sqrt = (int) Math.sqrt(area);
            int length = sqrt; // 大
            int width = sqrt; // 小
            while (length <= area && width >= 1) { 
                if (length * width == area) return new int[]{ length, width};
                else if (length * width > area) width--;
                else length++;
            }
            return null;
        }

#### 方法3：O(n)，最快解法 ####

看了别人的 0ms 的解法如下。不知道这个解法为什么会比双指针耗时更少。

public int[] constructRectangle(int area) { 
            int mid = (int) Math.sqrt(area);
            while (true) { 
                if (area % mid == 0) { 
                    return new int[]{ area / mid,mid};
                } else { 
                    mid--;
                }
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_construct-the-rectangle]: https://leetcode-cn.com/problems/construct-the-rectangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221021/db4529af2fdc4a0c9c3c1417ec4e260f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221021/3dec03c860d74d83afcc9c1765d1d25a.png