[LeetCode] Max Points on a Line

2024-06-05 08:58

文章标签 leetcode line max points

本文主要是介绍[LeetCode] 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.

解题思路
若两个点共线，则有如下情况：
- 两个点重合
- 两个点的x坐标相同（斜率无穷大）
- 两个点的斜率相同
  y1 = k * x1 + b;
  y2 = k * x2 + b;
  则有k = (y1 - y2) / (x1 - x2);
实现代码

/******************************************************************  @Author   : 楚兴*  @Date     : 2015/2/9 20:46*  @Status   : Accepted*  @Runtime  : 35 ms
******************************************************************/
#include <vector>
#include <unordered_map>
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) {if (points.size() <= 2){return points.size();}int maxNum = 0;unordered_map<double,int> mymap;int copy;  //重复的点个数double k;  //斜率for (int i = 0; i < points.size(); i++){mymap.clear();copy = 0;  //坐标相同点的个数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){copy++;  //相同点continue;}if (points[i].x == points[j].x){mymap[INT_MAX]++; //斜率不存在}else {k = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);mymap[k]++;}}if (mymap.size() == 0){maxNum = maxNum > copy ? maxNum : copy;}int temp;for (auto it = mymap.cbegin(); it != mymap.cend(); it++){temp = (*it).second + copy;maxNum = maxNum > temp ? maxNum : temp;}}return maxNum + 1;  //加上自身}
};int main()
{Solution s;vector<Point> points;Point* p1 = new Point(0, 0);Point* p2 = new Point(0, 0);points.push_back(*p1);points.push_back(*p1);cout<<s.maxPoints(points)<<endl;delete p1;delete p2;system("pause");
}