LeetCode刷题实战149：直线上最多的点数-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 直线上最多的点数，我们先来看题面：

https://leetcode-cn.com/problems/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.

题意

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

样例

解题

https://blog.csdn.net/qq_17550379/article/details/83035798

这个问题我们有一个最简单的思路，就是我们先从所有点中找出两个点，然后用这两个点构成一条直线，然后再计算有多少点在这个直线上，我们记录它。接着找下一条直线，直到我们计算完所有直线对应的点的个数。这种解法的时间复杂度是O(n^3)，显然太慢了，而且实际操作起来也很麻烦。

我们知道一个线段是由斜率和截距决定的，实际上如果我们知道了一个直线上的点和这条直线的斜率也能确定这条直线。基于此，我们可以遍历所以点point，计算其余点和point构成的直线的斜率，如果斜率相同，那么说明两个点在一条直线上，我们只要记录点的个数，最后找到最大值即可。对于上述算法我要注意一个问题，就是存在相同点的情况，我们需要对此加以处理。

from collections import defaultdict
class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        slopes, result = defaultdict(int), 0
        for i, point1 in enumerate(points): 
            slopes.clear()
            duplicate = 1
            for _, point2 in enumerate(points[i+1:]):
                if point1.x == point2.x and point1.y == point2.y:
                    duplicate += 1
                    continue

                slope = float('inf') if point1.x == point2.x else \
                            (point1.y - point2.y)/(point1.x - point2.x)

                slopes[slope] += 1

            if result < duplicate:
                result = duplicate

            for _, val in slopes.items():
                if val + duplicate > result:
                    result = val + duplicate

        return result