题目描述

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

在二维平面上，有一些点，请找出经过点数最多的那条线。
给定一个点集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是要查找的对象，该方法返回查找对象的索引位置，如果没有找到对象则抛出异常。