939. Minimum Area Rectangle

Description

Here

Intuition

这题其实只有O(N^2)的solution,别想太多

直接任取两点,假装是对角线的两点,检查possible 的另外两个点是否存在,如果存在,计算最小矩形

Optimal Solution

其实可以按照每一行分类,然后orderly 取两点,作为一条边,看是否之前出现过,如果出现过,可以作为一个矩形计算面积

这个其实可以控制到O(N^1.5)

O((number of x) * (number of x) * (number of y)) < O(N^1.5)

Reference-80ms)

Pitfall

Solution

results matching ""

    No results matching ""