LeetCode149 直线上最多的点数

发表于 | 分类于 |
字数统计: 229 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/max-points-on-a-line/

题面

给定一些二维坐标中的点，求同一条线上最多由多少点。

解法

暴力的话三重循环 也可以通过但是效率不高
一个比较好的解法使用map存每两个点的斜率 然后计算斜率相同的个数
对于斜率不存在的情况要单独拿出来处理
不是很难的一道题目

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 0;
        if (n <= 1) return n;
        unordered_map<double, int> k;
        for (int i = 0; i < n; i++) {
            int same_x = 0;
            for (int j = i + 1; j < n; j++) {
                vector<int> p1(points[i]), p2(points[j]);
                if (p1[0] == p2[0]) {
                    same_x++;
                }
                else {
                    k[(double)(p2[1] - p1[1]) / (p2[0] - p1[0])]++;
                }
            }
            ans = max(ans, same_x + 1);
            for (auto item: k) {
                ans = max(ans, 1 + item.second);
            }
            k.clear();
        }
        return ans;
    }
};