内容简介:给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上示例1:
题目描述
给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上
示例1:
输入: [[1,1],[2,2],[3,3]] 输出: 3 解释: ^ | | o | o | o +-------------> 0 1 2 3 4
示例2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出: 4 解释: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6
算法
func maxPoints(points []Point) int { n := len(points) // diffMap 用来过滤掉相同的点,并记录他们的个数 //map特点: point1和point2,不是同一个对象,但是X和Y属性值相同,则key相等 diffMap := make(map[Point]int, n) for i := 0; i < n; i++ { diffMap[points[i]]++ } size := len(diffMap) // 不超过 2 个不同的点 // 则,所有的点都在同一条直线上 if size <= 2 { return n } max := 0 // 存在相同的点, // 则,提取所有不同的点,可以大大减少后面 3 个嵌套的 for 循环的次数 if size < n { points = make([]Point, 0, size) for p := range diffMap { points = append(points, p) } } for i := 0; i < size-1; i++ { for j := i + 1; j < size; j++ { count := 0 // 所有的点,都要检查,是否与 i, j 共线 for k := 0; k < size; k++ { if isSameLine(points[i], points[j], points[k]) { count += diffMap[points[k]] } } if max < count { max = count } } } return max } func isSameLine(p1, p2, p3 Point) bool { //高中数学中,判断第三个点在某条线上 //(p3.Y-p1.Y)/(p3.X-p1.X) == (p2.Y-p1.Y)/(p2.X-p1.X),则p3在p1-p2线上 return (p3.X-p1.X)*(p2.Y-p1.Y) == (p2.X-p1.X)*(p3.Y-p1.Y) }
个人思路
1. 任意不同的两点确定一条直线,遍历所有点是否在该线上,并计数 2. []Point中有重复的点,所以首先得利用map去重并分别记录点的个数,可以大大减少多层for循环中判断三点是否同一直线的次数, 3. 不同点不超过2个,则所有点在同一条线上
总结
- 笔者前期采用的思路是,公式 y=ax+b,斜率a相等,且b相等,则是同一直线,然后以(a,b)为key,只需遍历一遍[]Point,一层for循环,看似简单,但是写到后面,发现代码非常的复杂,且存在a为0或b为0等各种特殊情况,数据结构复杂,a为float64,有精度问题
- 目前版本算法,直接使用3层for循环,看似复杂度很高,但是可以先去重,减少for次数,以及代码直白简单,易懂的特点
- 好的代码,应该思路清晰,读者容易看懂,与君共勉
GitHub
- 项目源码在这里
- 笔者会一直维护该项目,对leetcode中的算法题进行解决,并写下自己的思路和见解,致力于人人都能看懂的算法
个人公众号
- 喜欢的朋友可以关注,谢谢支持
- 记录90后 码农 的学习与生活
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据结构与算法分析
韦斯 (Mark Allen Weiss) / 陈越 / 机械工业出版社 / 2016-3-1 / 69.00元
本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。本书把算法分析与有效率的Java程序的开发有机地结合起来,深入分析每种算法,内容全面、缜密严格,并细致讲解精心构造程序的方法。一起来看看 《数据结构与算法分析》 这本书的介绍吧!