149. 直线上最多的点数

Difficulty
Hard
Tags
几何
数学
URL
https://leetcode.cn/problems/max-points-on-a-line/
Star
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1：
notion imagenotion image
输入：points = [[1,1],[2,2],[3,3]]
输出：3
示例 2：
notion imagenotion image
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
提示：
  • 1 <= points.length <= 300
  • points[i].length == 2
  • 104 <= xi, yi <= 104
  • points 中的所有点 互不相同
通过次数61,542提交次数166,469

法1 hash (O(n**2))

思路
遍历每一个点，然后找以该点为中心，其余点与该点的的斜率。
题解
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)

        res = 0
        for i in range(0, len(points)):
            slope = defaultdict(int)
            x1, y1 = points[i]

            for j in range(i+1, len(points)):
                x2, y2 = points[j]

                dx = x2 - x1
                dy = y2 - y1

                if dx == 0:
                    slope["#"] += 1
                else:
                    slope[round(dy / dx, 4)] += 1

            res = max(res, 1 + max(list(slope.values()) + [0]))

        return res
 

法2 暴力遍历 O(n**3)

notion imagenotion image
notion imagenotion image
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)
        res = 2
        for i in range(0, len(points)):
            for j in range(i+1, len(points)):
                count = 2
                for k in range(j+1, len(points)):
                    if self.helper(points, i, j, k):
                        count += 1

                res = max(res, count)

        return res

    def helper(self, points, i, j, k):
        p1, p2, p3 = points[i], points[j], points[k]
        return (p3[1]-p1[1]) * (p2[0]-p1[0]) == (p3[0]-p1[0]) * (p2[1]-p1[1])