首页 > 代码库 > 【Leetcode】Max Points on a Line

【Leetcode】Max Points on a Line

2024-07-07 16:17:09   228人阅读

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 };

 


联系
我们