数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python程序：计算位于同一条直线上的点的数量
假设我们有一组坐标。每个坐标有两个值x和y，代表笛卡尔平面上的一个点。现在找到位于同一条直线上的点的最大数量。
因此，如果输入类似于coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]，则输出为4，因为点[1, 1]，[2, 2]，[6, 6]，[7, 7]位于同一条直线上。
为了解决这个问题，我们将遵循以下步骤：
res := 0
对于 i 从 0 到 points 列表的大小，执行：
(x1, y1) := points[i]
slopes := 一个新的映射
same := 1
对于 j 从 i + 1 到 points 列表的大小，执行：
(x2, y2) := points[j]
如果 x2 等于 x1，则
slopes[inf] := 1 + (如果 slopes[inf] 存在，则为 slopes[inf]，否则为 0)
否则，如果 x1 等于 x2 且 y1 等于 y2，则
same := same + 1
否则，
slope := (y2 - y1) / (x2 - x1)
slopes[slope] := 1 + (如果 slopes[slope] 存在，则为 slopes[slope]，否则为 0)
如果 slopes 不为空，则
res := res 和 (same + slopes 所有值的列表的最大值) 中的最大值
返回 res
示例
让我们看看下面的实现来更好地理解：
class Solution:
def solve(self, points):
res = 0
for i in range(len(points)):
x1, y1 = points[i][0], points[i][1]
slopes = {}
same = 1
for j in range(i + 1, len(points)):
x2, y2 = points[j][0], points[j][1]
if x2 == x1:
slopes[float("inf")] = slopes.get(float("inf"), 0) + 1
elif x1 == x2 and y1 == y2:
same += 1
else:
slope = (y2 - y1) / (x2 - x1)
slopes[slope] = slopes.get(slope, 0) + 1
if slopes:
res = max(res, same + max(slopes.values()))
return res
ob = Solution()
coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
print(ob.solve(coordinates))输入
[[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
输出
4
更新于：2020-12-22
567 次浏览
广告