149. Max Points on a Line
Question
Given an array of
points
wherepoints[i] = [x<sub>i</sub>, y<sub>i</sub>]
represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Solution
首先选取一个点,然后创建哈希表。记录这个点与其他点的斜率关系与出现次数。记录一个出现次数最多的max值,如果当前次数大于max则更新max。
注意计算斜率时对y == 0和 x == 0时要返回无穷大和0,否则会有精度问题。
最后返回max + 1。
可以优化的地方是,当max大于总点数的一半,或者max大于剩余的点时,因为已经找到了最大的max值,可以直接返回答案。
Code
1 | class Solution { |
叉乘计算可以判断两个向量是否重合。
由于叉乘乘积($|a||b|sinθ$)的模等于两个向量组成的平行四边形的面积,因此当两者乘积为0时,则两个向量重合。
点乘乘积得到的是向量在另一个向量上的投影的乘积,$|a||b|cosθ$
149. Max Points on a Line
https://xuanhe95.github.io/2022/05/06/149-Max-Points-on-a-Line/