首页 > 代码库 > Max Points on a Line

Max Points on a Line

Max Points on a Line

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

c++版本:

/**  * 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) {          // IMPORTANT: Please reset any member data you declared, as          // the same Solution instance will be reused for each test case.          unordered_map<float,int> mp;          int maxNum = 0;          for(int i = 0; i < points.size(); i++)          {              mp.clear();              mp[INT_MIN] = 0;              int duplicate = 1;              for(int j = 0; j < points.size(); j++)              {                  if(j == i) continue;                  if(points[i].x == points[j].x && points[i].y == points[j].y)                  {                      duplicate++;                      continue;                  }                  float k = points[i].x == points[j].x ? INT_MAX : (float)(points[j].y - points[i].y)/(points[j].x - points[i].x);                  mp[k]++;              }              unordered_map<float, int>::iterator it = mp.begin();              for(; it != mp.end(); it++)                  if(it->second + duplicate > maxNum)                      maxNum = it->second + duplicate;          }          return maxNum;      }  };  

  java版本:

/** * Definition for a point. * class Point { *     int x; *     int y; *     Point() { x = 0; y = 0; } *     Point(int a, int b) { x = a; y = b; } * } */public class Solution{    public int maxPoints(Point[] points) {       if(points.length == 0 || points == null)             return 0;       if(points.length == 1)           return 1;        int max = 1;        for(int i = 0; i < points.length; i++){            int same = 0;            int localmax = 1;            HashMap<Float, Integer> fm = new HashMap<Float, Integer>();            for(int j = 0; j < points.length; j++) {                if(i == j)                   continue;                                   if(points[i].x == points[j].x && points[i].y == points[j].y) {                    same ++;                    continue;                }                                float slop = ((float)(points[i].x - points[j].x)/(points[i].y - points[j].y));                                if(fm.containsKey(slop))                     fm.put(slop, fm.get(slop) + 1);                else                    fm.put(slop, 2);            }                 for(Integer value : fm.values())                   localmax = Math.max(localmax, value);                                        localmax += same;                   max = Math.max(max,localmax);        }        return max;    }}    

  

Max Points on a Line