题目描述

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

题目大意

平面上有n个点，找出共线的点的最大个数

解题思路

很容易想到O(n^3)的解法，通过起点i，终点j枚举直线，然后枚举中间点k，依次判断k与i,j是否共线，统计最大值。

实际上，采用此题可以采用O(n^2 * log(n))的复杂度解答，思路为：枚举起点i，与终点j，依次计算i，j的斜率，统计斜率相同的点的个数的最大值（另外需要考虑起点终点重合的情况）。此法实际上采用了起点分组统计的思想，因此减少了一重循环。

Python代码如下：

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

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        ans = 0
        size = len(points)
        for x in range(size):
            k_dict = {}
            same = 0
            for y in range(x + 1, size):
                if self.isEqual(points[x], points[y]):
                    same += 1
                else:
                    k = self.getK(points[x], points[y])
                    if k_dict.get(k) is None:
                        k_dict[k] = 1
                    else:
                        k_dict[k] += 1
            val = 0
            if len(k_dict):
                val = max(k_dict.values())
            ans = max(ans, val + same + 1)
        return ans
    def getK(self, pa, pb):
        if pa.x == pb.x:
            return None
        return 1.0 * (pb.y - pa.y) / (pb.x - pa.x)
    def isEqual(self, pa, pb):
        return pa.x == pb.x and pa.y == pb.y

 

本文链接：http://bookshadow.com/weblog/2014/10/16/leetcode-max-points-line/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码