题目描述

题目地址: 穿点最多的直线

在二维平面上,有一些点,请找出经过点数最多的那条线。
给定一个点集vector p和点集的大小n,没有两个点的横坐标相等的情况,请返回一个vector,代表经过点数最多的那条直线的斜率和截距。

点集中p的定义为:

1
2
3
4
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b

实现思路

在数学知识中,如果直线L1经过了点a和点b,斜率为k1。直线L2经过了点c和点d,斜率为k2。如果k1和k2相等,那就说明L1和L2是在同一条直线L上的,且直线L经过点a,b,c,d。

实现思路图示

过程描述

遍历点集中的任意两个点p1和p2,并计算p1和p2的斜率,然后将斜率放入字典,字典中key为斜率,value为该斜率出现的次数,每当有相同的斜率出现时,该斜率次数加1。最后统计字典中value最大的值,即相同斜率次数最多的,那么该斜率代表的直线就是平面上经过点数最多的直线。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# -*- coding:utf-8 -*-
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
class DenseLine:
def getLine(self, p, n):
# write code here
max_line = 0
max_slope = None
max_intercept = None
slope_dict = {}
for i in range(n-1):
for j in range(i+1, n):
k = 1.0 * (p[j].y - p[i].y) / (p[j].x - p[i].x)
if k in slope_dict:
slope_dict[k] += 1
else:
slope_dict[k] = 1
for item in slope_dict:
if slope_dict[item] > max_line:
max_line = slope_dict[item]
max_slope = item
max_intercept = p[i].y - item * p[i].x
return max_slope, max_intercept
# 运行时间:133ms
# 占用内存:5856k

看别人提交的代码,还有更简洁的实现,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class DenseLine:
def getLine(self, p, n):
# write code here
lines=[]
counts=[]
for i in range(n-1):
# k斜率, b截距
k = (p[i+1].y - p[i].y)/(p[i+1].x - p[i].x)
b = p[i].y-p[i].x*k
lines.append((k,b))
for i in lines:
counts.append(lines.count(i))
return lines[counts.index(max(counts))]
# 运行时间:95ms
# 占用内存:5624k

lines列表中以元组的形式保存两点之间连线的斜率和截距(k,b)

在第12行,lines.count(i)会返回列表中第i(k,b)出现的次数,比如列表中的截距假设为:
lines = [(1,2), (3, 4), (5,6),(1,2)],那么count()方法返回的结果是:counts[2,1,1,2]

在第13行,统计counts列表中的最大值,即相同(k,b)的个数,然后用index()方法返回counts列表中最大值第一个匹配项的索引位置,根据索引位置返回lines列表中相同次数最多的(k,b),该斜率代表的直线就是平面上经过点数最多的直线。

这里面涉及到列表的两个小知识点:

count()方法,用于统计某个元素在列表中出现的次数。 语法为: list.count(obj)
obj是列表中要统计的对象,返回值是该元素在列中中出现的次数。

index()方法,用于从列表中找出某个值的第一个匹配项的索引位置。 语法: list.index(obj)
obj是要查找的对象,该方法返回查找对象的索引位置,如果没有找到对象则抛出异常。