0149. Max Points on a Line¶
题目信息¶
- 题号:
直线上最多的点数
- 难度:
Hard
- 主题:
几何、斜率规范化、最大公约数、哈希计数
- 原题:
- 重点:
固定锚点把直线比较降为方向分组,用约分后的整数对精确表示同一无向斜率
题目重述¶
给定二维平面上一组互不重复的整数点 points,返回能同时位于同一条直线上的最大点数。直线可以水平、
竖直或具有任意有理斜率;只统计输入点。
自建示例¶
[[-2,-1], [0,0], [2,1], [4,2], [0,3]]:前四点都满足y = x / 2,返回4;[[3,-2], [3,1], [3,5], [-1,5], [6,5]]:竖线x=3与水平线y=5都含三个点, 返回3;[[0,0], [-2,-1], [2,1]]:从锚点看两个方向相反,但属于同一条直线,必须放入同一方向桶。
C++ 实现¶
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <unordered_map>
#include <utility>
#include <vector>
struct DirectionHash {
std::size_t operator()(
const std::pair<int, int>& direction
) const noexcept {
const std::uint64_t first = static_cast<std::uint32_t>(
direction.first
);
const std::uint64_t second = static_cast<std::uint32_t>(
direction.second
);
return static_cast<std::size_t>((first << 32) ^ second);
}
};
class Solution {
private:
int verifyEveryLine(
const std::vector<std::vector<int>>& points
) {
const int pointCount = static_cast<int>(points.size());
if (pointCount <= 2) {
return pointCount;
}
int best = 2;
for (int first = 0; first < pointCount; ++first) {
for (int second = first + 1;
second < pointCount;
++second) {
const long long deltaX =
points[second][0] - points[first][0];
const long long deltaY =
points[second][1] - points[first][1];
int onLine = 0;
for (int candidate = 0;
candidate < pointCount;
++candidate) {
const long long candidateX =
points[candidate][0] - points[first][0];
const long long candidateY =
points[candidate][1] - points[first][1];
if (deltaX * candidateY == deltaY * candidateX) {
++onLine;
}
}
best = std::max(best, onLine);
}
}
return best;
}
std::pair<int, int> normalizedDirection(int deltaX, int deltaY) {
if (deltaX == 0) {
return {1, 0};
}
if (deltaY == 0) {
return {0, 1};
}
const int divisor = std::gcd(deltaX, deltaY);
deltaX /= divisor;
deltaY /= divisor;
if (deltaX < 0) {
deltaX = -deltaX;
deltaY = -deltaY;
}
return {deltaY, deltaX};
}
int countDirectionsFromEveryAnchor(
const std::vector<std::vector<int>>& points
) {
const int pointCount = static_cast<int>(points.size());
int best = pointCount == 0 ? 0 : 1;
for (int anchor = 0; anchor < pointCount; ++anchor) {
std::unordered_map<
std::pair<int, int>,
int,
DirectionHash
> frequency;
int largestBucket = 0;
for (int other = 0; other < pointCount; ++other) {
if (other == anchor) {
continue;
}
const int deltaX =
points[other][0] - points[anchor][0];
const int deltaY =
points[other][1] - points[anchor][1];
const auto direction = normalizedDirection(deltaX, deltaY);
largestBucket = std::max(
largestBucket,
++frequency[direction]
);
}
best = std::max(best, largestBucket + 1);
}
return best;
}
public:
int maxPoints(std::vector<std::vector<int>>& points) {
return countDirectionsFromEveryAnchor(points);
}
};
题解¶
原始搜索:两点定线,再验证所有点¶
任意两个不同点唯一确定一条直线。最直接的 verifyEveryLine 枚举点对 A、B,再检查每个候选
P 是否满足叉积等式:
(Bx - Ax) * (Py - Ay) == (By - Ay) * (Px - Ax)
等式不需要除法,水平线和竖直线都适用;代码用 long long 计算乘积,避免坐标差相乘溢出。这种方法
正确,但同一条含 k 个点的直线会被它的许多点对反复定义,每次又扫描全部 n 个点,时间
O(n^3)。
固定锚点后,直线只剩方向¶
固定输入点 A。所有经过 A 的直线可按方向分组:若 B-A 与 C-A 是同一无向方向,那么
A、B、C 共线;方向不同则对应不同的过 A 直线。于是一次扫描其他点并统计最大方向桶,就
得到“经过当前锚点的最多点数”;桶计的是其他点,最后还要加锚点自身。
遍历每个锚点即可覆盖全局最优直线。任取最优线上的一个输入点作锚点,其余同线点都会落在同一个方向桶,
所以不会漏解。与点对定线相比,共线关系从“每对重复验证全部点”压缩为“每个锚点给其他点分桶”,期望
时间降为 O(n^2)。
为什么不能直接用 double 斜率作键¶
斜率 deltaY / deltaX 本质是有理数。数学上相等的比例经过浮点除法后依赖舍入表示;竖线还要处理除零,
水平线可能出现正零与负零。即使当前坐标范围下许多例子恰好通过,浮点键也没有提供精确的等价类证明。
整数方向向量可以精确规范化。先用 gcd(deltaX, deltaY) 同时约分,得到互质分量;再规定非竖直方向的
deltaX 必须为正,若为负就同时翻转两个分量。这样 (2,1)、(4,2) 与 (-2,-1) 都统一为
(deltaY, deltaX) = (1,2)。
水平线与竖直线为何单独规范¶
同一竖线上,从锚点向上可能得到 (0, positive),向下得到 (0, negative);它们必须属于同一条线,
统一键设为 (1,0)。水平线对称统一为 (0,1)。先处理这两类也避免最大公约数和符号规则出现零分量
歧义。
原始 |
规范键 |
含义 |
|---|---|---|
|
|
斜率 |
|
|
反方向但同一直线 |
|
|
竖直线 |
|
|
水平线 |
哈希状态与具体走读¶
对锚点 [0,0] 和其他点 [-2,-1]、[2,1]、[4,2]、[0,3],前三个方向都规范为
(1,2),该桶计数为三;竖直点进入 (1,0) 桶。当前锚点所在最大直线含 3 + 1 = 4 个点。
输入保证点互不重复,所以不会出现 deltaX == 0 && deltaY == 0 的“重复点”状态;若约束允许重复点,
必须另设计数并把它加到每个锚点答案,不能把零向量归入某个方向桶。这里不为不存在的状态增加代码分支。
DirectionHash 只负责把规范整数对组合成哈希值;方向相等性仍由 std::pair 的精确整数比较决定,哈希
碰撞不会错误合并不同方向,容器会继续检查键相等。
正确性与复杂度¶
固定锚点时,同一规范键的点与锚点共线;任意经过锚点的共线点又具有成比例方向,经约分和符号统一后键相同, 所以桶与过锚点直线一一对应。遍历全部锚点后,全局最大值必被统计。
主解共有 n 个锚点,每个扫描 n-1 个点;最大公约数和哈希操作按坐标位宽计为常数,期望时间
O(n^2)、单个锚点的哈希空间 O(n)。三点叉积基线时间 O(n^3)、额外空间 O(1),保留它用于
展示重复定义同一直线的瓶颈;主解选择精确整数方向哈希。