esc to dismiss

149. 直线上最多的点数

题目

给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1:

输入:points = [[1,1],[2,2],[3,3]]

输出:3

示例 2:

输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

输出:4

解题思路

本题的关键在于如何判断三个或三个以上的点在一条直线上。根据几何公理:平面上两点决定一条直线。判断第三点在不在这条直线上,只要看这个点与直线上的一点组成的直线斜率与原来的直线是不是一样。因为一样的话:要么这两条直线重叠,要么两条直线平行。而原直线上的一点不可能在两条平行直线上,因此这两条直线只能重叠。

因此,这个题目可以转换成以两个点作为基准直线,再去判断其他点在不在这条直线上,统计在同一直线上的个数,遍历这种组合,直到找出最大值。这种算法的复杂度为 O(n^3).

直线斜率计算很简单,比如两个点 p1(p1.x, p1.y) 和 p2(p2.x, p2.y) 组成的直线斜率为:

(p2.x - p1.x)/(p2.y - p1.y)

只要比较斜率一致即可,但这个计算公式是除法,而除法会有精度丢失的问题,因此要将除法转换为乘法,比如判断 p1(p1.x, p1.y) , p2(p2.x, p2.y) , p3(p3.x, p3.y) 是否在一条之间上:

如果:

(p2.x - p1.x)/(p2.y - p1.y) == (p3.x - p1.x)/(p3.y - p1.y)

根据乘除法互换率,得到:

(p2.x - p1.x) * (p3.y - p1.y) == (p3.x - p1.x) * (p2.y - p1.y)

代码如下:

func maxPoints(points [][]int) int {
    total := len(points)
    if total <= 2 {
        return total
    }

    maxCount := 0
    for i, p1 := range points {
        for j, p2 := range points {
            if maxCount*2 > total {
                return maxCount
            }

            if i == j {
                continue
            }

            count := 2
            for k, p3 := range points {
                if k == i || k == j {
                    continue
                }

                s1 := (p3[1] - p1[1]) * (p3[0] - p2[0])
                s2 := (p3[0] - p1[0]) * (p3[1] - p2[1])
                if s1 == s2 {
                    count++
                }
            }
            if count > maxCount {
                maxCount = count
            }
        }
    }

    return maxCount
}

上面代码中加了一个小优化,即如果有一半以上的点在一条线上,那这条线肯定是最多的点了,不用再往下找了。

这个方法比较容易理解,但算法时间复杂度为 O(n^3)。 LeetCode 官方题解网友宫水三叶的题解 通过哈希表做优化,可以达到 O(n^2 * log m) 的时间复杂度。不过我看了一会也没明白,有机会再研究吧。

经验教训

略。

x