C++ code with hashmap ,beating 96% others


  • 2
    S
    int maxPoints(vector<Point>& points) {
            int len = points.size(), ans = 0;
            if(len <= 2) return len;
            unordered_map<double, int> mp;
            for(int i = 0; i < len; i++){
                int dup = 1;    // To count the points exactly same with point i, including i itself.
                mp.clear();
                for(int j = i+1; j < len; j++){   // we start with j = i +1, because lines from i to k (k = 0,1,...,i-1) has already been considered in the previous steps.
                    if(points[i].x == points[j].x && points[i].y == points[j].y){
                            dup++;
                            continue;
                    }
                    else{
                        float slope = (points[i].x == points[j].x) ? INT_MAX : (float(points[i].y-points[j].y)/(points[i].x-points[j].x));
                        mp[slope]++;
                    }
                }
                ans = max(dup , ans);  // in case no element in the map.
                for (auto slope : mp)
                    if (slope.second + dup > ans) 
                        ans = slope.second + dup; 
            }
             return ans;
    }
    

    Idea: For one single point, we calculate the slopes to each of others and store them in a hash map. Take care of the case INT_MAX and duplicate.


Log in to reply
 

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