[Leetcode]149. Max Points on a Line(C++)

题目描述

题目链接：149. 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

Input: [[1,1],[2,2],[3,3]] Output: 3

例子 2

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4

解题思路

解这道题一个简单的思路是通过两两遍历所有点对，并构造对应直线方程。通过哈系表存储所有可能直线包含的点的下标（不能是坐标因为可能有重合点），最后取包含点的最多的直线方程（中包含点的个数）即可。定义一条直线方程需要两个参数（斜率和截距），所以需要用二维哈希表。代码如下：

#include <vector>
#include <unordered_map>
#include <unordered_set>

class Solution {
public:
    int maxPoints(std::vector<std::vector<int>>& points) {
        
        if (points.size() < 3) return points.size();
        
        std::unordered_map<long double, std::unordered_map<long double, std::unordered_set<int>>> line_points;
        std::unordered_map<long double, std::unordered_set<int>> vertical_points;
        int curMax = 0;
        
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                long double x1 = points[i][0], y1 = points[i][1];
                long double x2 = points[j][0], y2 = points[j][1];
                
                if (x1 == x2) { // x1 == x2, its on vertical line
                    vertical_points[x1].insert(i);
                    vertical_points[x1].insert(j);
                    curMax = std::max((int)vertical_points[points[i][0]].size(), curMax);
                    continue;
                }
                
                long double slope = (y1 - y2) / (x1 - x2);
                long double offset = y1 - slope * x1;
                line_points[slope][offset].insert(i);
                line_points[slope][offset].insert(j);
                curMax = std::max((int)line_points[slope][offset].size(), curMax);
                
            }
        }
        
        return curMax;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(n)

GitHub 代码同步地址： 149.MaxPointsOnALine.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions