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

在这里插入图片描述

文章目录

- 前言
- 摘要
- 问题描述
- 解题思路
- 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 中的所有点 互不相同

解题思路

斜率定义
两点共线可以通过斜率判断。如果两点的斜率相等，则它们位于同一条直线上。斜率公式为：
[
slope = \frac{\Delta y}{\Delta x}
]
使用最大公约数（GCD）将分子和分母化简，以避免浮点误差。
双重循环
对于每个点，计算其与其他所有点的斜率，将斜率存入哈希表，并统计每种斜率的出现次数。
处理重复点和垂直线
- 如果点重合，直接计入重复点数。
- 如果两点垂直，则斜率无穷大，可单独处理。

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
}

代码分析

核心逻辑
- 使用哈希表存储斜率及其出现次数，避免重复计算。
- 每次遍历后更新最大点数。
斜率化简
- 使用最大公约数（GCD）将斜率标准化，避免浮点误差或精度问题。
处理特殊情况
- 对于重复点，将它们合并计入最终结果。
- 对于垂直线，使用分母为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