首页 > 代码库 > 【Leetcode】Max Points on a Line
【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.
每次固定一个点,然后遍历所有其它点,记录每种斜率出现的次数。需要考虑两种特殊情况:斜率不存在和点与固定点重合。
1 /** 2 * Definition for a point. 3 * struct Point { 4 * int x; 5 * int y; 6 * Point() : x(0), y(0) {} 7 * Point(int a, int b) : x(a), y(b) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 int maxPoints(vector<Point> &points) { 13 int n = points.size(); 14 if (n <= 2) { 15 return n; 16 } 17 int ans = 2; 18 for (int i = 0; i < n - 1; ++i) { 19 Point o = points[i]; 20 unordered_map<double, int> k_cnt; //斜率出现计数 21 int v_cnt = 0; //垂直线上点计数(含重合点) 22 int dup_cnt = 0; //与固定点重合的点计数 23 for (int j = i + 1; j < n; ++j) { 24 Point p = points[j]; 25 if (p.x == o.x) { 26 ++v_cnt; //垂直线上的点 27 if (p.y == o.y) { 28 ++dup_cnt; //与固定点重合的点 29 } 30 } 31 else { 32 double k = ((double)p.y - o.y) / (p.x - o.x); 33 if (k_cnt.find(k) != k_cnt.end()) { 34 ++k_cnt[k]; 35 } 36 else { 37 k_cnt[k] = 1; 38 } 39 } 40 } 41 for (auto &c : k_cnt) { 42 if (c.second + dup_cnt + 1 > ans) { 43 ans = c.second + dup_cnt + 1; 44 } 45 } 46 if (v_cnt + 1 > ans) { 47 ans = v_cnt + 1; 48 } 49 } 50 return ans; 51 } 52 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。