149. 直线上最多的点数
题目描述
输入数组 points，points[i] = [xi, yi] 是平面上的一个整数坐标点，各点互不相同。
在所有可能的直线中，找出经过给定点最多的那一条，返回它经过的点数。只有一个点时答案为 1。
示例 1
输入：points = [[1,1],[2,2],[3,3]] 输出：3
解释：三个点都在直线 y = x 上。
示例 2
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出：4
解释：[3,2]、[4,1]、[2,3]、[1,4] 都在直线 x + y = 5 上。
数据范围
1 <= points.length <= 300points[i].length == 2-10^4 <= xi, yi <= 10^4- 所有点互不相同。
解题思路：枚举起点 + 斜率哈希
一条直线由一个点和一个斜率确定。依次把每个点 i 当作锚点，计算它与后面每个点 j 的方向 (dx, dy)，用哈希表统计每个方向出现的次数：同一方向的点和锚点共线。为了避免浮点误差，把 (dx, dy) 除以最大公约数化成最简形式，并统一符号（dx > 0，或 dx = 0 时 dy > 0），这样同一条直线的方向只有一种写法。
为什么正确
处理锚点 i 时，cnt[(dx, dy)] 等于已扫描的点中与 i 在方向 (dx, dy) 上共线的点数；该直线上的点数为 cnt + 1。
复杂度分析
时间 O(n² log C)（log C 来自求最大公约数），空间 O(n)。
易错点
用浮点数 dy/dx 表示斜率会有精度问题，dx = 0 还会除零。另外 (2,-2) 和 (-1,1) 是同一方向，必须约分并统一符号后再作为键。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
if n <= 2:
return n
best = 0
for i in range(n):
cnt = {}
x1, y1 = points[i]
for j in range(i + 1, n):
dx = points[j][0] - x1
dy = points[j][1] - y1
g = math.gcd(dx, dy)
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
cnt[(dx, dy)] = cnt.get((dx, dy), 0) + 1
best = max(best, cnt[(dx, dy)] + 1)
return bestclass Solution {
private int gcd(int a, int b) {
return b == 0 ? Math.abs(a) : gcd(b, a % b);
}
public int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2) {
return n;
}
int best = 0;
for (int i = 0; i < n; i++) {
Map<String, Integer> cnt = new HashMap<>();
int x1 = points[i][0], y1 = points[i][1];
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - x1;
int dy = points[j][1] - y1;
int g = gcd(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) {
dx = -dx; dy = -dy;
}
String key = dx + "," + dy;
cnt.put(key, cnt.getOrDefault(key, 0) + 1);
best = Math.max(best, cnt.get(key) + 1);
}
}
return best;
}
}class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 2) {
return n;
}
int best = 0;
for (int i = 0; i < n; i++) {
map<pair<int, int>, int> cnt;
int x1 = points[i][0], y1 = points[i][1];
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - x1;
int dy = points[j][1] - y1;
int g = gcd(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) {
dx = -dx; dy = -dy;
}
cnt[{dx, dy}]++;
best = max(best, cnt[{dx, dy}] + 1);
}
}
return best;
}
};func gcd149(a, b int) int {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}
func maxPoints(points [][]int) int {
n := len(points)
if n <= 2 {
return n
}
best := 0
for i := 0; i < n; i++ {
cnt := map[[2]int]int{}
x1, y1 := points[i][0], points[i][1]
for j := i + 1; j < n; j++ {
dx := points[j][0] - x1
dy := points[j][1] - y1
g := gcd149(dx, dy)
dx /= g
dy /= g
if dx < 0 || (dx == 0 && dy < 0) {
dx, dy = -dx, -dy
}
cnt[[2]int{dx, dy}]++
if cnt[[2]int{dx, dy}]+1 > best {
best = cnt[[2]int{dx, dy}] + 1
}
}
}
return best
}const gcd149 = (a, b) => b === 0 ? Math.abs(a) : gcd149(b, a % b);
/**
* @param {number[][]} points
* @return {number}
*/
var maxPoints = function(points) {
const n = points.length;
if (n <= 2) {
return n;
}
let best = 0;
for (let i = 0; i < n; i++) {
const cnt = new Map();
const [x1, y1] = points[i];
for (let j = i + 1; j < n; j++) {
let dx = points[j][0] - x1;
let dy = points[j][1] - y1;
const g = gcd149(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx === 0 && dy < 0)) {
dx = -dx; dy = -dy;
}
const key = dx + ',' + dy;
cnt.set(key, (cnt.get(key) || 0) + 1);
best = Math.max(best, cnt.get(key) + 1);
}
}
return best;
};const gcd149 = (a: number, b: number): number => b === 0 ? Math.abs(a) : gcd149(b, a % b);
function maxPoints(points: number[][]): number {
const n = points.length;
if (n <= 2) {
return n;
}
let best = 0;
for (let i = 0; i < n; i++) {
const cnt = new Map<string, number>();
const [x1, y1] = points[i];
for (let j = i + 1; j < n; j++) {
let dx = points[j][0] - x1;
let dy = points[j][1] - y1;
const g = gcd149(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx === 0 && dy < 0)) {
dx = -dx; dy = -dy;
}
const key = dx + ',' + dy;
cnt.set(key, (cnt.get(key) || 0) + 1);
best = Math.max(best, cnt.get(key)! + 1);
}
}
return best;
}其他解法
两种方法都枚举起点并约分斜率；哈希表计数平均 O(1)，整体更快；排序后数相同段不依赖哈希，常数稍大。
解法 2：枚举起点 + 斜率排序 时间 O(n² log n)，空间 O(n)
固定起点 i，对每个 j > i 求方向向量 (dx, dy)，用最大公约数约分并统一符号。把这些方向向量排序，相同方向会相邻。统计最长的相同段，长度加 1 就是经过点 i 的直线上最多的点数。
不需要哈希表，也不用为二元组设计哈希键，适合不方便用二元组做键的语言。多一个排序的 log n 因子，n 不超过 300 时差别不大。
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
if n <= 2:
return n
best = 0
for i in range(n):
x1, y1 = points[i]
dirs = []
for j in range(i + 1, n):
dx = points[j][0] - x1
dy = points[j][1] - y1
g = math.gcd(dx, dy)
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
dirs.append((dx, dy))
dirs.sort()
run = 0
for k in range(len(dirs)):
if k > 0 and dirs[k] == dirs[k - 1]:
run += 1
else:
run = 1
best = max(best, run + 1)
return bestclass Solution {
private int gcd(int a, int b) {
return b == 0 ? Math.abs(a) : gcd(b, a % b);
}
public int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2) return n;
int best = 0;
for (int i = 0; i < n; i++) {
int x1 = points[i][0], y1 = points[i][1];
int[][] dirs = new int[n - i - 1][];
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - x1;
int dy = points[j][1] - y1;
int g = gcd(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
dirs[j - i - 1] = new int[]{dx, dy};
}
Arrays.sort(dirs, (p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
int run = 0;
for (int k = 0; k < dirs.length; k++) {
if (k > 0 && dirs[k][0] == dirs[k - 1][0] && dirs[k][1] == dirs[k - 1][1]) run++;
else run = 1;
best = Math.max(best, run + 1);
}
}
return best;
}
}class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 2) return n;
int best = 0;
for (int i = 0; i < n; i++) {
int x1 = points[i][0], y1 = points[i][1];
vector<pair<int, int>> dirs;
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - x1;
int dy = points[j][1] - y1;
int g = gcd(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
dirs.push_back({dx, dy});
}
sort(dirs.begin(), dirs.end());
int run = 0;
for (int k = 0; k < (int)dirs.size(); k++) {
if (k > 0 && dirs[k] == dirs[k - 1]) run++;
else run = 1;
best = max(best, run + 1);
}
}
return best;
}
};func gcdSort149(a, b int) int {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}
func maxPoints(points [][]int) int {
n := len(points)
if n <= 2 {
return n
}
best := 0
for i := 0; i < n; i++ {
x1, y1 := points[i][0], points[i][1]
dirs := [][2]int{}
for j := i + 1; j < n; j++ {
dx := points[j][0] - x1
dy := points[j][1] - y1
g := gcdSort149(dx, dy)
dx /= g
dy /= g
if dx < 0 || (dx == 0 && dy < 0) {
dx, dy = -dx, -dy
}
dirs = append(dirs, [2]int{dx, dy})
}
sort.Slice(dirs, func(p, q int) bool {
if dirs[p][0] != dirs[q][0] {
return dirs[p][0] < dirs[q][0]
}
return dirs[p][1] < dirs[q][1]
})
run := 0
for k := range dirs {
if k > 0 && dirs[k] == dirs[k-1] {
run++
} else {
run = 1
}
if run+1 > best {
best = run + 1
}
}
}
return best
}const gcdSort149 = (a, b) => b === 0 ? Math.abs(a) : gcdSort149(b, a % b);
var maxPoints = function(points) {
const n = points.length;
if (n <= 2) return n;
let best = 0;
for (let i = 0; i < n; i++) {
const [x1, y1] = points[i];
const dirs = [];
for (let j = i + 1; j < n; j++) {
let dx = points[j][0] - x1;
let dy = points[j][1] - y1;
const g = gcdSort149(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
dirs.push([dx, dy]);
}
dirs.sort((p, q) => p[0] !== q[0] ? p[0] - q[0] : p[1] - q[1]);
let run = 0;
for (let k = 0; k < dirs.length; k++) {
if (k > 0 && dirs[k][0] === dirs[k - 1][0] && dirs[k][1] === dirs[k - 1][1]) run++;
else run = 1;
best = Math.max(best, run + 1);
}
}
return best;
};const gcdSort149 = (a: number, b: number): number => b === 0 ? Math.abs(a) : gcdSort149(b, a % b);
function maxPoints(points: number[][]): number {
const n = points.length;
if (n <= 2) return n;
let best = 0;
for (let i = 0; i < n; i++) {
const [x1, y1] = points[i];
const dirs: number[][] = [];
for (let j = i + 1; j < n; j++) {
let dx = points[j][0] - x1;
let dy = points[j][1] - y1;
const g = gcdSort149(dx, dy);
dx /= g;
dy /= g;
if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
dirs.push([dx, dy]);
}
dirs.sort((p, q) => p[0] !== q[0] ? p[0] - q[0] : p[1] - q[1]);
let run = 0;
for (let k = 0; k < dirs.length; k++) {
if (k > 0 && dirs[k][0] === dirs[k - 1][0] && dirs[k][1] === dirs[k - 1][1]) run++;
else run = 1;
best = Math.max(best, run + 1);
}
}
return best;
}