C++ 32ms O(nlgn) Solution


  • 0
    J
    
        bool Comp (const pair<int, int>& p1, const pair<int, int>& p2) {
            if (p1.first != p2.first)
                return p1.first < p2.first;
            else
                return p1.second > p2.second;
        }
        
    class Solution {
        
    public:
        bool isReflected(vector<pair<int, int>>& points) {
            
            int len = points.size();
            if (len == 0) return true;
            
            sort(points.begin(), points.end());
            
            // remove duplicates
            int i = 0;
            for (int j = 1; j < len; j++) {
                if (points[i] != points[j]) {
                    swap(points[++i], points[j]);
                }
            }
            
            len = i + 1;
            if (len == 1) return true;
            
            
            double split = 0.0; 
            int left, right, mid = len >> 1;
            if (len & 1) {
                split = points[mid].first;
                left = mid - 1;
                right = mid + 1;
            } else {
                split = (points[mid - 1].first + points[mid].first) / 2.0;
                left = mid - 1;
                right = mid;
            }
            
            //resort the right part
            sort(points.begin() + right, points.begin() + len, Comp);
            
            for (;left >= 0 && right < len; left--, right++) {
                
                double lx = split - points[left].first;
                double rx = points[right].first - split;
    
                if (lx != rx || (lx != 0 && points[left].second != points[right].second))
                    return false;
            }
                
            
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.