首页 > 其他 > 详细

LeetCode: Max Points on a Line

时间:2014-02-22 22:41:40      阅读:487      评论:0      收藏:0      [点我收藏+]

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

bubuko.com,布布扣
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        //key is slope, value is the number of points in the line of a given slope
        //this map will be reused
        if (points.size() <= 1){
            return points.size();
        }
        unordered_map<double, int> slopeMap;
        int result = 0;
        for (unsigned i = 0; i < points.size(); i++){
            slopeMap.clear();
 
            Point anchorPoint = points[i];
            int dupPointCount = 0;
            int dupLineCount = 1;
            for (unsigned j = i + 1; j < points.size(); j++){
                Point currentPoint = points[j];
                //same point should be count in every line
                if (anchorPoint.x == currentPoint.x && anchorPoint.y == currentPoint.y){
                    dupPointCount++;
                } else {//not same point
                    double slope = std::numeric_limits<double>::infinity();
                    if (anchorPoint.x != currentPoint.x){//avoid divide 0 error
                        slope = (double)(anchorPoint.y - currentPoint.y) / (anchorPoint.x - currentPoint.x);
                    }
                    if (slopeMap.find(slope) == slopeMap.end()){//slope first appear
                        slopeMap[slope] = 1;
                    }
                    slopeMap[slope]++;
                    int currentLinePointCount = slopeMap[slope];
                    if (currentLinePointCount > dupLineCount){
                        dupLineCount = currentLinePointCount;
                    }
                }
            }
            if (dupLineCount + dupPointCount > result){
                result = dupLineCount + dupPointCount;
            }
        }
        return result;
    }
};
bubuko.com,布布扣

 

LeetCode: Max Points on a Line

原文:http://www.cnblogs.com/yeek/p/3560828.html

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