216 - 149 直线上最多的点数

题目

给定一个二维平面，平面上有 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

解答

感觉可以，任意两点做直线，看有多少点在这根直线上

https://leetcode-cn.com/problems/max-points-on-a-line/solution/pythonzhu-shi-xiang-shi-on2suan-fa-si-kao-guo-chen/

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        from collections import defaultdict

        def clac(points, i):
            hashmap = defaultdict(int)
            same = 0
            for j in range(0, len(points)):
                if j != i:
                    if points[i] == points[j]:
                        same += 1
                        continue
                    if points[i][1] - points[j][1] == 0:
                        k = float('inf')
                    else:
                        k = (points[i][0] - points[j][0]) / (points[i][1] -
                                                             points[j][1])
                    hashmap[k] += 1
            return 1 + same + (max(hashmap.values()) if hashmap else 0)

        res = 0
        if len(points) == 1:
            return 1
        for i in range(len(points)):
            res = max(res, clac(points, i))
        return res

Runtime: 72 ms, faster than 67.14% of Python3 online submissions for Max Points on a Line.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Max Points on a Line.