

LeetCode: 149. 直线上最多的点数

• LeetCode: 149. 直线上最多的点数
  • 1、题目描述
  • 2、解题思路

1、题目描述

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

示例 1:

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

示例 2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

2、解题思路

• 这个题目主要是基于斜率进行判断
• 首先做一下去重
• 首先是节点a，对其他所有节点判断一次斜率，将斜率相同的加起来
• 然后将a点移除，然后重新选择一个节点，执行上面的操作，直到集合中只有一个元素为止

import fractions
import collections


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        count = collections.Counter([tuple(p) for p in points])
        if len(count) <= 2:
            return len(points)
        length = len(count)

        ans = 0
        for _ in range(1, length):
            (x, y), nums = count.popitem()
            slope = collections.defaultdict(lambda: nums)

            for (m, n), c in count.items():
                if x == m and y != n:
                    slope["0/" + str(x)] += c
                elif x != m and y == n:
                    slope[str(y) + "/0"] += c
                else:
                    slope[str(fractions.Fraction(n - y, m - x))] += c

            ans = max(ans, max(slope.values()))

        return ans