leetcode——149. Max points on a Line

 题目要求：

    Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

解法：

    

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return n; // 如果点的数量小于等于2，直接返回点的数量
        
        int maxPoints = 0;
        
        for (int i = 0; i < n; ++i) {
            unordered_map<double, int> slopeCount; // 用于存储斜率及其频率
            int samePointCount = 1; // 记录和当前点重合的点数量
            
            for (int j = 0; j < n; ++j) {
                if (i == j) continue; // 跳过与自己相同的点
                
                // 计算斜率，特殊处理斜率为无穷大的情况
                double slope = points[i][1] == points[j][1] ?
                               std::numeric_limits<double>::infinity() :
                               (double)(points[j][0] - points[i][0]) / (points[j][1] - points[i][1]);
                
                // 更新斜率频率
                slopeCount[slope]++;
            }
            
            // 计算经过当前点的直线上最多的点数
            for (auto& pair : slopeCount) {
                maxPoints = max(maxPoints, pair.second + samePointCount);
            }
            
            // 更新重合点的数量
            maxPoints = max(maxPoints, samePointCount);
        }
        
        return maxPoints;
    }
};
	
	
	

...