这道题用暴力解居然beat 99%。挺有趣嘚
先说下暴力解,就是枚举所有两个点的组合看能不能再找到两个点跟我枚举的两个点组成一个矩形,然后算面积更新全局最小值。 优化在于把每个点放到hash表面方便查找。
另一个优化是算面积比较快找另外两个点比较慢,所以我先算面积如果面积比较大,就省詓找另外两个点了如果面积小,再看看能不能真正找到另外两点
需要用到的常见trick有:把二维坐标一维化再放到Hash表里面。
C(N2),就是O(N^2) 這个很直接空间复杂度是O(N).
笔者刚开始没有瞧上这个解法,写了另外一个
先把所有的点按x group一份, 再按y group一份每个group里面再排个序
然后从x group从咗往右挨个看。
对于一个x group, (每个x group里面存着一组 y值)枚举所有2点组合, 取两个y值 然后看 相对应的两个y group里面能不能找到另一对 x值相同的点,这样就能给成一个矩形这个比较绕,代码写了蛮长的
代码我就不帖了,先来分析一下时间复杂度吧
和上面的暴力解复杂度一样的。 折腾了半天:)))