LeetCode 149 Max Points on a Line

    
        标签：
        
            LeetCode
        
    发布于：2022-03-02 16:58:37
    编辑于：2022-03-02 17:17:22
    浏览量：793

概述

https://leetcode.com/problems/max-points-on-a-line/

这是一道 Hard 题。

暴力法

利用哈希表为每条直线维护其上点的个数。

怎么去重好嘞。

那就把点也存一下吧。

实现的时候注意：

points 为 1 的时候直接返回 1。
y = kx + b 无法处理与 y 轴平行的情况。

下面的 double k = double (b[1] - a[1]) / double (b[0] - a[0]); 实际上有除 0 的风险，但是没报错欸。

class Solution {
public:
    unordered_map<double, unordered_map<double, set<vector<int>*>>> m;
    int ans = 0;
    int maxPoints(vector<vector<int>>& points) {
        if (points.size() == 1) return 1;
        for (int i = 0; i < points.size(); i ++) {
            for (int j = 1; j < points.size(); j ++) {
                helper(points[i], points[j]);
            }
        }
        return ans;
    }
    
    void helper(vector<int>& a, vector<int>& b) {
        double k = double (b[1] - a[1]) / double (b[0] - a[0]);
        double n = a[1] - k * a[0];
        if (b[0] == a[0]) {
            k = INT_MAX;
            n = b[0];
        }
        m[k][n].insert(&a);
        m[k][n].insert(&b);
        ans = max(ans, int(m[k][n].size()));
    }
};

Links: leetcode-149-max-points-on-a-line