题目:
难度:Hard
相关话题:哈希表
、数学
给定一个二维平面,平面上有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
思路:
原理:两点确定一条直线。
- 确定第一个点。
确定第二个点,如果第二个点和第一个点相同,则继续选择下一个第二个点。
注意:
根据前面亮点的dx=p2.x-p1.x
和dy=p2.y-p1.y
,确定后续的其他点。
注意:
- 当存在
dx===0
或者dy===0
,直接判断p3.x-p1.x
或者p3.y-p1.y
是否为0
。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Definition for a point.
* function Point(x, y) {
* this.x = x;
* this.y = y;
* }
*/
/**
* @param {Point[]} points
* @return {number}
*/
var maxPoints = function(points) {
let maxLen=0
for(let i=0;i<points.length;i++){
// 确定第一个点
let first=points[i]
let count=1
// if(maxLen===0)maxLen=1
for(let j=0;j<points.length;j++){
if(i===j)continue
count++
// 确定第二个点,如果第二个点和第一个点相同,则继续选择下一个第二个点
let sec=points[j]
let dx=sec.x-first.x,dy=sec.y-first.y
if(dx===0 && dy===0)continue
for(let k=j+1;k<points.length;k++){
// 通过前面2个点的间隔,筛选后面的点
if(k===i)continue
let o=points[k]
let deltX=o.x-first.x,
deltY=o.y-first.y
if(dx===0 && deltX===0)count++
else if(dy===0 && deltY===0)count++
else if(deltX/deltY===dx/dy)count++
}
maxLen=Math.max(maxLen,count)
count=1
}
maxLen=Math.max(maxLen,count)
}
return maxLen
};