当前位置： 面试刷题>> 直线上最多的点数(经典算法150题)
### 题目描述
题目：**直线上最多的点数**
给定一个二维平面上的点集，每个点由一对整数坐标 `(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 代码示例
```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 代码示例
```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 代码示例
```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;
}
```
以上代码示例中，我们遍历了所有点对，并计算了它们之间的斜率（或特殊表示方式），以此来判断它们是否在同一直线上。最终，我们返回了构成最多点数的直线上的点数。