首页 > 其他 > 详细

LeetCode "Line Reflection"

时间:2016-06-15 06:54:27      阅读:224      评论:0      收藏:0      [点我收藏+]

First you find the Y, and then do a pairing game - hashtable is good.

技术分享
class Solution {
public:
    bool isReflected(vector<pair<int, int>>& points)
    {
        int n = points.size();
        if (n < 2) return true;

        unordered_map<int, unordered_map<int, int>> hm; // y - [x, cnt]
        int minx = INT_MAX, maxx = INT_MIN;
        for (auto &pr : points)
        {
            minx = min(minx, pr.first);
            maxx = max(maxx, pr.first);

            hm[pr.second][pr.first] ++;
        }
        if (minx == maxx) return true;

        int midx2 = (minx + maxx);
        for (auto &pr : points)
        {
            int x = pr.first;
            int y = pr.second;

            // paired already?
            if (hm.find(y) == hm.end() || hm[y].find(x) == hm[y].end()) 
                continue;
            
            if (x * 2 == midx2)
            {
                hm[y].erase(x);
            }
            else
            {
                int x2 = midx2 - x;
                if (hm[y].find(x2) != hm[y].end())
                {
                    hm[y][x] --;
                    if (!hm[y][x])    hm[y].erase(x);
                    
                    hm[y][x2] --;
                    if (!hm[y][x2])    hm[y].erase(x2);
                }
            }

            if (!hm[y].size())    hm.erase(y);
        }

        return hm.empty();
    }
};
View Code

LeetCode "Line Reflection"

原文:http://www.cnblogs.com/tonix/p/5586102.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!