0149. Max Points on a Line ========================== 题目信息 -------- :题号: 0149. 直线上最多的点数 :难度: Hard :主题: 几何、斜率规范化、最大公约数、哈希计数 :原题: `LeetCode 0149 `_ :重点: 固定锚点把直线比较降为方向分组,用约分后的整数对精确表示同一无向斜率 题目重述 -------- 给定二维平面上一组互不重复的整数点 ``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++ 实现 -------- .. code-block:: cpp #include #include #include #include #include #include struct DirectionHash { std::size_t operator()( const std::pair& direction ) const noexcept { const std::uint64_t first = static_cast( direction.first ); const std::uint64_t second = static_cast( direction.second ); return static_cast((first << 32) ^ second); } }; class Solution { private: int verifyEveryLine( const std::vector>& points ) { const int pointCount = static_cast(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 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>& points ) { const int pointCount = static_cast(points.size()); int best = pointCount == 0 ? 0 : 1; for (int anchor = 0; anchor < pointCount; ++anchor) { std::unordered_map< std::pair, 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>& points) { return countDirectionsFromEveryAnchor(points); } }; 题解 ---- 原始搜索:两点定线,再验证所有点 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 任意两个不同点唯一确定一条直线。最直接的 ``verifyEveryLine`` 枚举点对 ``A``、``B``,再检查每个候选 ``P`` 是否满足叉积等式: .. code-block:: text (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)``。先处理这两类也避免最大公约数和符号规则出现零分量 歧义。 .. list-table:: :header-rows: 1 * - 原始 ``(deltaX, deltaY)`` - 规范键 ``(deltaY, deltaX)`` - 含义 * - ``(4, 2)`` - ``(1, 2)`` - 斜率 ``1/2`` * - ``(-2, -1)`` - ``(1, 2)`` - 反方向但同一直线 * - ``(0, 5)``、``(0, -3)`` - ``(1, 0)`` - 竖直线 * - ``(6, 0)``、``(-4, 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)``,保留它用于 展示重复定义同一直线的瓶颈;主解选择精确整数方向哈希。