题目描述

题目：直线上最多的点数

给定一个二维平面上的点集，每个点由一对整数坐标 (x, y) 表示。现在，我们需要找出这些点中，能构成最多点数的直线（即，在同一直线上的点数最多）。返回这条直线上点的数量。

注意：

1. 两点确定一条直线，但如果三点或更多点共线，则这些点都视为在同一直线上。
2. 坐标值在 int 范围内。
3. 输入的点集中不包含重复的点。

示例

输入：[[1,1],[2,2],[3,3]] 输出：3 解释：这三个点在同一直线上。

输入：[[1,1],[2,2],[3,4],[1,0],[4,5],[2,1]] 输出：2 解释：最长直线是 (1,1) 和 (2,2)，或者 (2,1) 和 (4,5)，它们都包含2个点。

解题思路

为了解决这个问题，我们可以使用哈希表来存储斜率（或直线的另一种表示方式）和对应的点数。对于每一点，我们计算它与其他所有点形成的斜率（为了避免分母为0的情况，可以使用 y2-y1 除以 x2-x1 的方式，如果 x 坐标相同，则直接比较 y 坐标）。然后，我们使用这些斜率（或特定表示方式）来更新哈希表中对应直线的点数。

PHP 代码示例

function maxPoints($points) {
    $n = count($points);
    if ($n <= 2) {
        return $n;
    }
    
    $maxCount = 0;
    for ($i = 0; $i < $n; $i++) {
        $slopes = [];
        $duplicatePoints = 0;
        $maxCurrent = 0;
        
        for ($j = $i + 1; $j < $n; $j++) {
            if ($points[$i][0] == $points[$j][0] && $points[$i][1] == $points[$j][1]) {
                $duplicatePoints++;
                continue;
            }
            
            $x1 = $points[$i][0];
            $y1 = $points[$i][1];
            $x2 = $points[$j][0];
            $y2 = $points[$j][1];
            
            if ($x1 == $x2) {
                $slope = 'INF'; // 垂直线
            } else {
                $slope = ($y2 - $y1) . '/' . ($x2 - $x1);
            }
            
            if (!isset($slopes[$slope])) {
                $slopes[$slope] = 1;
            } else {
                $slopes[$slope]++;
            }
            
            $maxCurrent = max($maxCurrent, $slopes[$slope]);
        }
        
        $maxCount = max($maxCount, $maxCurrent + $duplicatePoints + 1);
    }
    
    return $maxCount;
}

Python 代码示例

def maxPoints(points):
    n = len(points)
    if n <= 2:
        return n
    
    max_count = 0
    for i in range(n):
        slopes = {}
        duplicate_points = 0
        max_current = 0
        
        for j in range(i + 1, n):
            if points[i] == points[j]:
                duplicate_points += 1
                continue
            
            x1, y1 = points[i]
            x2, y2 = points[j]
            
            if x1 == x2:
                slope = 'INF'
            else:
                slope = (y2 - y1) / (x2 - x1)
            
            slopes[slope] = slopes.get(slope, 0) + 1
            max_current = max(max_current, slopes[slope])
        
        max_count = max(max_count, max_current + duplicate_points + 1)
    
    return max_count

JavaScript 代码示例

function maxPoints(points) {
    const n = points.length;
    if (n <= 2) return n;
    
    let maxCount = 0;
    for (let i = 0; i < n; i++) {
        const slopes = {};
        let duplicatePoints = 0;
        let maxCurrent = 0;
        
        for (let j = i + 1; j < n; j++) {
            if (points[i][0] === points[j][0] && points[i][1] === points[j][1]) {
                duplicatePoints++;
                continue;
            }
            
            const [x1, y1] = points[i];
            const [x2, y2] = points[j];
            
            let slope;
            if (x1 === x2) {
                slope = 'INF';
            } else {
                slope = `${(y2 - y1)}/${(x2 - x1)}`;
            }
            
            if (!slopes[slope]) {
                slopes[slope] = 1;
            } else {
                slopes[slope]++;
            }
            
            maxCurrent = Math.max(maxCurrent, slopes[slope]);
        }
        
        maxCount = Math.max(maxCount, maxCurrent + duplicatePoints + 1);
    }
    
    return maxCount;
}

以上代码示例中，我们遍历了所有点对，并计算了它们之间的斜率（或特殊表示方式），以此来判断它们是否在同一直线上。最终，我们返回了构成最多点数的直线上的点数。