当前位置：网站首页>LeetCode149-直线上最多的点数-数学-哈希表

LeetCode149-直线上最多的点数-数学-哈希表

2022-04-23 14:48:00 【李烦烦搞快点】

原题链接
在这里插入图片描述

Note：

枚举所有的点，让他作为原点

选定原点之后，再去找一遍所有的点，这时候分为三种情况
1、与当前原点重合的点（可以看做任意斜率直线上面的点）
2、垂直直线上的点（这时候斜率是算不了的，除数不能为0）
3、正常的点，构成一条斜率存在的直线的点

然后每个点按照斜率来分类，最后首先检查一下斜率正常的点和垂直直线上的点谁多
然后在看看 答案 和 这次遍历后比较多的点 + 重合的点 谁多

第二次遍历的时候，肯定会有个重合的点啊，就是当前的点，这不是重复了？
是在第二次遍历的时候才计数的，不会算多的

代码如下：

class Solution {
    
public:
    int maxPoints(vector<vector<int>>& points) {
    
        int ans = 0;
        for(auto& p: points){
    
            int s = 0, v = 0;
            unordered_map<long double, int> cnt;
            for(auto& q : points){
    
                if(p == q)    s ++;
                else if(p[0] == q[0])   v ++;
                else{
    
                    long double k = (long double) (q[1] - p[1]) / (q[0] - p[0]);
                    cnt[k] ++;
                }
            }
            int c = v;
            for(auto [k, v] : cnt)  c = max(c, v);
            ans = max(ans, c + s);
        }
        return ans;
    }
};

版权声明
本文为[李烦烦搞快点]所创，转载请带上原文链接，感谢
https://blog.csdn.net/Mr_Ghost812/article/details/124348976

边栏推荐

猜你喜欢

随机推荐