文章目录

Max Points On A Line 坐标系中一条直线上的最多点数题目解题思路代码实现

Max Points On A Line 坐标系中一条直线上的最多点数

题目

给出一组坐标系的点，求出能连成一条直线的最多点数

解题思路

将坐标点 p₁ 的 x₁ 与 y₁ 的值，依次与后面的坐标点 p_n的 x_n 与 y_n 做差值并相除（(x₁ - x_n) / (y₁ - y_n)）得出两点之间的斜率若有其他坐标点 p_m 与坐标点 p₁ 的斜率相同，则 p₁ 、 p_n 、 p_m 在一条直线上有两个特殊情况 由于 y 的差值为除数，所以若差为 0 即为不合理数，且此时的两点是处于同一水平线上的，将此情况单独摘出，独立计算点数当有相同坐标点存在时，即所有与此坐标点相关的连线点数都适用，亦可独立记重复点数，在比较最大点数时再加上去 记录并更新当前最大点数从 p₂ 开始依次向后重复操作，

代码实现

class func MaxPointOnLineSolution(points:[[Int]]) -> Int{ let count = points.count // 当坐标点数量小于3时，最多点数即为坐标点数量 if(count<3){ return count; } // 声明最多点数 var maxPoint = 0 // 外层循环，用以拿到比较的坐标点 for pointFK in 0 ..< count-1 { // 获取比较的坐标点 let pf = points[pointFK] // 以斜率为key，被比较的坐标点数为value，声明一个dictionary var map = [Double:Int]() // 声明变量用以记录相同的被比较坐标点数 var samePointNum = 0 // 声明变量用以记录y差值为0，即在同一水平线的d被比较坐标点数 var line = 0 // 声明变量记录此次外层循环中，除两种特殊情况的最多的被比较坐标点数 var currentMaxPoint = 0 // 内层循环，用以拿到被比较的坐标点 for pointTK in pointFK+1 ..< count { // 获取被比较的坐标点 let pt = points[pointTK] // 计算两点的x、y的差值 let vx = Double(pt[0]-pf[0]) let vy = Double(pt[1]-pf[1]) var key = Double(0) if(vx != 0 && vy == 0){ //当y的差值为0时，水平点数+1，并跳过此次循环 line += 1 continue }else if(vx == 0 && vy == 0){ //当两点重复时，记录相同点数，并跳过此次循环 samePointNum += 1 continue }else{ //计算斜率 key = vx/vy } if(map.keys.contains(key)){ //若斜率的key已存在，将value 点数 +1 map[key]! += 1; }else{ //若斜率的key不存在，则创建key map[key] = 1; } // 更新当前外层循环中，除两种特殊情况的最多的被比较坐标点数 if(map[key]! > currentMaxPoint){ currentMaxPoint = map[key]! } } // 与水平点数比较并更新当前外层循环的最多点数 currentMaxPoint = currentMaxPoint > line ? currentMaxPoint : line // 将相同点数以及比较坐标点计算到当前外层循环的最多点数 currentMaxPoint += samePointNum + 1 // 更新最终的最多点数 maxPoint = currentMaxPoint > maxPoint ? currentMaxPoint : maxPoint } return maxPoint }

代码地址：https://github.com/sinianshou/EGSwiftLearning