Max Points on a Line

题目描述

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

解题方法

最naive的解法

正常表示一条直线应该是用

y= mx + b
m - slope
b - y-intercept

但是这样找出在同一条直线上的点太过复杂，需要O(n^3)的时间

• 确定起点i, 终点j，得出上面的公式 O(N^2)
• 对其他的每一点，用公式判断它是否在直线上 O(N)

改进解法

用hashtable记录对同一个起点出现过的斜率，用空间换时间

• 对每一点i, 确定它为起点，计算每一点对它的斜率slope，用hashmap记录出现过的斜率的点数
• 如果与点i重合，那么应该和所有斜率在同一条直线上
• 如果斜率出现过，那么斜率相同的点必然在同一条直线上
• 对起点i记录下以它为起点的一条直线上最多的点

loop每一个点作为起点，再loop除了它以为之后的点（前面的点作为起点已经算过），时间复杂度O(n^2)

Solution

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        if not points:
            return 0
        length = len(points)
        maxPoints = 1
        for i in range(length):
            slopeDic = {}
            same = 0
            for j in range(i+1,length):
                if points[i].x == points[j].x and points[i].y == points[j].y:
                    same += 1
                else:
                    slope = self.getSlope(points[i], points[j])
                    if slope in slopeDic:
                        slopeDic[slope] += 1
                    else:
                        slopeDic[slope] = 1
            if slopeDic:
                curMax = max(slopeDic.values()) + same + 1
            else:
                curMax = same + 1
            maxPoints = curMax if maxPoints < curMax else maxPoints
        return maxPoints

    def getSlope(self, p1, p2):
        if p1.x == p2.x:
            return "vertical"
        else:
            return 1.0 * (p2.y - p1.y) / (p2.x - p1.x)

Reference

• max points on a line