Hard

题目描述

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • 所有点都 不同

解题思路

这是一道几何问题，核心思想是：同一条直线上的所有点具有相同的斜率。

基本思路：

  1. 枚举每个点作为基准点
  2. 计算该基准点与其他所有点的斜率
  3. 使用哈希表统计相同斜率的点的个数
  4. 取所有情况中的最大值

关键技术点：

  1. 斜率计算：对于两点 (x1,y1) 和 (x2,y2)，斜率为 (y2-y1)/(x2-x1)
  2. 处理特殊情况：
    • 垂直线：x1 == x2，斜率为无穷大
    • 重合点：需要单独处理
  3. 精度问题：直接用浮点数计算斜率会有精度误差，更好的方法是用分数的形式存储斜率

优化方案：

  • 使用最大公约数(GCD)将斜率约简为最简分数形式
  • 用 (分子, 分母) 的二元组作为哈希表的键
  • 统一处理负数情况，确保分母为正

时间复杂度分析：

  • 外层循环：O(n)
  • 内层循环：O(n)
  • GCD计算：O(log(max coordinate))
  • 总体：O(n²)

代码实现

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return n;
        
        int maxCount = 2;
        
        for (int i = 0; i < n; i++) {
            map<pair<int, int>, int> slopeCount;
            int duplicate = 1; // 包含当前点本身
            
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                
                if (dx == 0 && dy == 0) {
                    duplicate++;
                    continue;
                }
                
                int g = gcd(dx, dy);
                dx /= g;
                dy /= g;
                
                // 确保分母为正
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
                
                slopeCount[{dy, dx}]++;
            }
            
            maxCount = max(maxCount, duplicate);
            for (auto& p : slopeCount) {
                maxCount = max(maxCount, p.second + duplicate);
            }
        }
        
        return maxCount;
    }
    
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        from math import gcd
        from collections import defaultdict
        
        n = len(points)
        if n <= 2:
            return n
        
        max_count = 2
        
        for i in range(n):
            slope_count = defaultdict(int)
            duplicate = 1  # 包含当前点本身
            
            for j in range(i + 1, n):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                
                if dx == 0 and dy == 0:
                    duplicate += 1
                    continue
                
                g = gcd(dx, dy)
                dx //= g
                dy //= g
                
                # 确保分母为正
                if dx < 0:
                    dx, dy = -dx, -dy
                
                slope_count[(dy, dx)] += 1
            
            max_count = max(max_count, duplicate)
            for count in slope_count.values():
                max_count = max(max_count, count + duplicate)
        
        return max_count

public class Solution {
    public int MaxPoints(int[][] points) {
        int n = points.Length;
        if (n <= 2) return n;
        
        int maxCount = 2;
        
        for (int i = 0; i < n; i++) {
            var slopeCount = new Dictionary<(int, int), int>();
            int duplicate = 1; // 包含当前点本身
            
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                
                if (dx == 0 && dy == 0) {
                    duplicate++;
                    continue;
                }
                
                int g = GCD(Math.Abs(dx), Math.Abs(dy));
                dx /= g;
                dy /= g;
                
                // 确保分母为正
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
                
                var slope = (dy, dx);
                slopeCount[slope] = slopeCount.GetValueOrDefault(slope, 0) + 1;
            }
            
            maxCount = Math.Max(maxCount, duplicate);
            foreach (var count in slopeCount.Values) {
                maxCount = Math.Max(maxCount, count + duplicate);
            }
        }
        
        return maxCount;
    }
    
    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}

var maxPoints = function(points) {
    if (points.length <= 2) return points.length;
    
    let maxCount = 0;
    
    for (let i = 0; i < points.length; i++) {
        let slopeMap = new Map();
        let duplicate = 1;
        let localMax = 0;
        
        for (let j = i + 1; j < points.length; j++) {
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
            
            if (dx === 0 && dy === 0) {
                duplicate++;
                continue;
            }
            
            let gcd = getGCD(dx, dy);
            dx /= gcd;
            dy /= gcd;
            
            if (dx < 0 || (dx === 0 && dy < 0)) {
                dx = -dx;
                dy = -dy;
            }
            
            let slope = dx + "," + dy;
            slopeMap.set(slope, (slopeMap.get(slope) || 0) + 1);
            localMax = Math.max(localMax, slopeMap.get(slope));
        }
        
        maxCount = Math.max(maxCount, localMax + duplicate);
    }
    
    return maxCount;
};

function getGCD(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² × log C)，其中 n 是点的个数，C 是坐标的最大值。外层循环 O(n)，内层循环 O(n)，每次需要计算 GCD 为 O(log C)
空间复杂度O(n)，哈希表最多存储 n 个不同的斜率

相关题目