使用 Swift 解决平面上同一条直线的最多点数
原创使用 Swift 解决平面上同一条直线的最多点数
原创
好事发生
文章推荐：架构设计：AI 驱动软件开发的基石
文章链接：https://cloud.tencent.com/developer/article/2474026
文章简介：本文介绍AI架构设计的基本概念，其对软件生命周期的影响，并通过 Python 实现的 Demo 代码提供实践指导，帮助开发者从零开始掌握 AI 架构设计。感兴趣的同学可以看看！
前言
本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。
不积跬步，无以至千里；不积小流，无以成江海，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 <= 300points[i].length == 2-104 <= xi, yi <= 104points中的所有点 互不相同
解题思路
- 斜率定义undefined两点共线可以通过斜率判断。如果两点的斜率相等，则它们位于同一条直线上。斜率公式为：undefined[ slope = \frac{\Delta y}{\Delta x} ]undefined使用最大公约数（GCD）将分子和分母化简，以避免浮点误差。
- 双重循环undefined对于每个点，计算其与其他所有点的斜率，将斜率存入哈希表，并统计每种斜率的出现次数。
- 处理重复点和垂直线
- 如果点重合，直接计入重复点数。
- 如果两点垂直，则斜率无穷大，可单独处理。
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测试结果
- 输入：
[[1, 1], [2, 2], [3, 3]]undefined输出：3 - 输入：
[[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]undefined输出：4
时间复杂度
- 外层循环：遍历每个点，复杂度为
O(n)。 - 内层循环：计算其他点的斜率，复杂度为
O(n)。undefined总复杂度：O(n^2)。
空间复杂度
- 哈希表的存储空间：
O(n)。undefined总复杂度：O(n)。
总结
本文通过基于斜率的哈希表法解决了二维平面上点共线问题。代码利用GCD优化斜率计算并处理特殊情况，既保证了精度，又提高了效率。通过完整的代码和详尽的分析，读者可以轻松掌握该问题的解决思路和实现细节。
关于我们
我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
