C++_Accepted_Set_46ms, 63.81%


  • 0

    Using set, the result is much better.
    time: 46ms, 63.81%

    class Solution {  
    public:  
    bool isReflected(vector<pair<int, int>>& points) {  
        set<pair<int, int>> st;  
        int Min = INT_MAX, Max = INT_MIN;  
        for(auto point : points){
            st.insert(point);
            Min = min(Min, point.first);
            Max = max(Max, point.first);
        }
        int x = Min + Max;//no need to >>2
        for(auto point : points){
            if(st.find(pair<int,int>(x - point.first, point.second)) == st.end()){return false;}
        }
        return true;
    }  
    };
    

    0_1476307920932_72191B82-40A9-4041-ACCD-8788CDE9A9EC.png

    Second-time try result: 69ms, 12.31%, it's still not satisfactory.

    class Solution {
    public:
    bool isReflected(vector<pair<int, int>>& points) {
        if(points.size() < 2) return true;
        
        map<pair<int,int>, int>mp;
        int minP = INT_MAX;
        int maxP = INT_MIN;
        
        for(int i = 0; i < points.size(); ++i){
            if(mp.find(points[i]) == mp.end()){
                mp.insert(pair<pair<int,int>,int>(points[i],0));
            }
            if(points[i].first > maxP){maxP = points[i].first;}
            if(points[i].first < minP){minP = points[i].first;}
        }
        
        int x = minP + maxP;
        
        for(int i = 0; i < points.size(); ++i){
            if(mp[points[i]] == 0){
                int a = x - points[i].first;
                int b = points[i].second;
                if(mp.find(pair<int,int>(a,b)) == mp.end()){return false;}
                else{
                    mp[pair<int,int>(a,b)] = 1;
                    mp[points[i]] = 1;
                }
            }
        }
        return true;
    }
    };
    

    Following is my first-time try solution. Although it has been accepted and straight forward, but the time is 79ms, which is 5.60%.

    class Solution {
    public:
    bool isReflected(vector<pair<int, int>>& points) {
        if(points.size() < 2) return true;
        
        map<pair<double,double>, int>mp;
        vector<pair<double, double>> double_points;
        int minP = INT_MAX;
        int maxP = INT_MIN;
        
        for(int i = 0; i < points.size(); ++i){
            pair<double,double> tmp(points[i].first * 1.0, points[i].second * 1.0);
            if(mp.find(tmp) == mp.end()){
                mp.insert(pair<pair<double,double>,int>(tmp,0));
                double_points.push_back(tmp);
            }
            if(points[i].first > maxP){maxP= points[i].first;}
            if(points[i].first < minP){minP = points[i].first;}
        }
        
        double x = (minP + maxP)/2.0;
        
        for(int i = 0; i < double_points.size(); ++i){
            if(mp[double_points[i]] == 0){
                double a = 2.0 * x - double_points[i].first;
                double b = double_points[i].second;
                if(mp.find(pair<double,double>(a,b)) == mp.end()){return false;}
                else{
                    mp[pair<double,double>(a,b)] = 1;
                    mp[double_points[i]] = 1;
                }
            }
        }
        return true;
    }
    };

Log in to reply
 

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