Swift解题 | 求平面上同一条直线的最多点数

前言

本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。

149. 直线上最多的点数

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

摘要

在平面几何中，找出最多的点共线是一个经典问题。本文详细解析如何使用Swift解决该问题，并基于斜率计算，逐步实现高效的算法解决方案。同时，提供可运行的代码模块及复杂度分析，帮助读者掌握这一算法的核心思想。

问题描述

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入： points = [[1,1],[2,2],[3,3]]
输出： 3

示例 2：

输入： points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出： 4

提示：

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• points 中的所有点 互不相同

解题思路

1. 斜率定义
   两点共线可以通过斜率判断。如果两点的斜率相等，则它们位于同一条直线上。斜率公式为：
   [
   slope = \frac{\Delta y}{\Delta x}
   ]
   使用最大公约数（GCD）将分子和分母化简，以避免浮点误差。

2. 双重循环
   对于每个点，计算其与其他所有点的斜率，将斜率存入哈希表，并统计每种斜率的出现次数。

3. 处理重复点和垂直线

   • 如果点重合，直接计入重复点数。
   • 如果两点垂直，则斜率无穷大，可单独处理。

Swift 实现代码

import Foundation

func maxPoints(_ points: [[Int]]) -> Int {
    guard points.count > 1 else { return points.count }

    var maxPointsOnLine = 1

    for i in 0..<points.count {
        var slopeCount = [String: Int]()
        var duplicates = 1
        var currentMax = 0

        for j in i+1..<points.count {
            let dx = points[j][0] - points[i][0]
            let dy = points[j][1] - points[i][1]

            if dx == 0 && dy == 0 {
                // 处理重复点
                duplicates += 1
                continue
            }

            // 计算简化的斜率
            let gcd = gcdOf(dx, dy)
            let simplifiedDx = dx / gcd
            let simplifiedDy = dy / gcd

            // 使用字符串作为键存储斜率
            let slopeKey = "\(simplifiedDx)/\(simplifiedDy)"
            slopeCount[slopeKey, default: 0] += 1
            currentMax = max(currentMax, slopeCount[slopeKey]!)
        }

        maxPointsOnLine = max(maxPointsOnLine, currentMax + duplicates)
    }

    return maxPointsOnLine
}

func gcdOf(_ a: Int, _ b: Int) -> Int {
    var a = abs(a), b = abs(b)
    while b != 0 {
        let temp = a % b
        a = b
        b = temp
    }
    return a
}

代码分析

1. 核心逻辑

   • 使用哈希表存储斜率及其出现次数，避免重复计算。
   • 每次遍历后更新最大点数。

2. 斜率化简

   • 使用最大公约数（GCD）将斜率标准化，避免浮点误差或精度问题。

3. 处理特殊情况

   • 对于重复点，将它们合并计入最终结果。
   • 对于垂直线，使用分母为0表示特殊斜率。

示例测试与结果

测试代码

let points1 = [[1, 1], [2, 2], [3, 3]]
let points2 = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]

print(maxPoints(points1)) // 输出: 3
print(maxPoints(points2)) // 输出: 4

测试结果

• 输入：[[1, 1], [2, 2], [3, 3]]
  输出：3
• 输入：[[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
  输出：4

时间复杂度

• 外层循环：遍历每个点，复杂度为O(n)。
• 内层循环：计算其他点的斜率，复杂度为O(n)。
  总复杂度：O(n^2)。

空间复杂度

• 哈希表的存储空间：O(n)。
  总复杂度：O(n)。

总结

本文通过基于斜率的哈希表法解决了二维平面上点共线问题。代码利用GCD优化斜率计算并处理特殊情况，既保证了精度，又提高了效率。通过完整的代码和详尽的分析，读者可以轻松掌握该问题的解决思路和实现细节。

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。