leetcode-149 | 直线上最多的点数

题目描述

给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。

示例:
输入: [[1,1],[2,2],[3,3]]
输出: 3

示例:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4

解答思路

受到上一题思路的影响(447),我们可以用循环,求出两个点之间的所有斜率,然后处理数据。
但是,对于斜率的处理,会有点麻烦,这里我们可以转换一下,如下图:

e

所以我们每次判断应该是三个点的判断,而不是两个点求斜率。
而且两个点验证的斜率并不靠谱,如下例:
[[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 ms23MBpython

   Reprint policy


《leetcode-149 | 直线上最多的点数》 by 梦否 is licensed under a Creative Commons Attribution 4.0 International License
 Previous
leetcode-219 | 存在重复元素 II leetcode-219 | 存在重复元素 II
题目描述给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例:输入: nums = [1,2,3,1], k = 3输
2019-05-03
Next 
leetcode-447 | 回旋镖的数量 leetcode-447 | 回旋镖的数量
题目描述给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭
2019-05-01
  TOC