题目描述
给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
示例:
输入: [[1,1],[2,2],[3,3]]
输出: 3
示例:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解答思路
受到上一题思路的影响(447),我们可以用循环,求出两个点之间的所有斜率,然后处理数据。
但是,对于斜率的处理,会有点麻烦,这里我们可以转换一下,如下图:
所以我们每次判断应该是三个点的判断,而不是两个点求斜率。
而且两个点验证的斜率并不靠谱,如下例:[[1,1], [4,1], [2,3], [5,3]]
不难发现是两条线,而且这样的例子会有很多。
翻译如下:
分析:
时间复杂度是:O(n^2),满足题意要求。
结果:
执行用时 : 1684 ms, 在Number of Boomerangs的Python3提交中击败了62.50% 的用户
内存消耗 : 23 MB, 在Number of Boomerangs的Python3提交中击败了13.46% 的用户
提交时间 | 状态 | 执行用时 | 内存消耗 | 语言 |
几秒前 | 通过 | 1684 ms | 23MB | python |