Ricky.L的随笔
0%

LeetCode.149.直线上最多的点数（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.149.直线上最多的点数（困难）

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

题解

暴力法梳理出整体框架，剩下细节问题和边界问题再填充。

算法步骤

  • 穷举所有可能形成的直线。
  • 统计有多少点在这一条直线上。
  • 记录最大的点数。

如何确定一个点是否在一条直线上？

已知点(x1, y1)和(x2, y2)确定的一条直线L。

判断点(x, y)是否在直线L上，可以判断点(x1, y1)和点(x, y)组成的直线的斜率是否与直线L的斜率相等。

换成数学表达式即判断 (y2 - y1) / (x2 - x1) == (y - y1) / (x - x1)。
其中两点不能是同一个点，x1不等于x。

斜率计算是浮点数，比较判断不准确怎么办？

  • 由于计算机除法存在数学精度问题，需要把上述表达式的比较，转换为对分子和分母分别比较。
  • 比较之前需要将分子分母约分到最简，进而就要求分子和父母的最大公约数。
  • 可使用辗转相除法来求最大公约数，约分分子、分母到最简。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
    fun maxPoints(points: Array<IntArray>): Int {
        if (points.isEmpty()) return 0
        // 一个点和两个点都是在同一个直线上
        if (points.size < 3) return points.size
        // 所有的点都是同一个点，表示所有的点都在同一条直线上
        if (points.distinctBy { "${it[0]},${it[1]}" }.size == 1) return points.size

        val n = points.size
        var maxPoints = 0
        for (i in 0 until n) {
            val x1 = points[i][0]
            val y1 = points[i][1]
            for (j in i + 1 until n) {
                val x2 = points[j][0]
                val y2 = points[j][1]
                // 同一个点确立不了直线，直接跳过，之后再确立了直线的情况，会考察到跳过的这个点
                if (x1 == x2 && y1 == y2) continue
                // (x1,y1)和(x2,y2)确立一条直线
                val line = Line(x1, y1, x2, y2)
                // 统计所有其他的点，是否在这条线上
                var tmpMax = 2
                for (k in 0 until n) {
                    if (k == i || k == j) continue
                    val x3 = points[k][0]
                    val y3 = points[k][1]
                    if (line.isOnTheLine(x3, y3)) {
                        // 发现有一个点在线上，计数
                        tmpMax++
                    }
                }
                if (tmpMax > maxPoints) {
                    maxPoints = tmpMax
                }
            }
        }
        return maxPoints
    }

    /**
     * 点([x1],[y1])和点([x2],[y2])确定一条直线
     * 直线的斜率为(y2-y1)/(x2-x1)
     * 限制条件：两点不能是同一个点，同时x1不等于x2
     */
    class Line(
            private val x1: Int,
            private val y1: Int,
            private val x2: Int,
            private val y2: Int
    ) {
        /**
         * 点([x],[y])是否在同一直线上
         *
         * 可判断点([x1],[y1])和点([x],[y])组成的直线斜率是否之前的直线相等
         * 换成数学表达式即 (y2-y1)/(x2-x1) == (y-y1)/(x-x1)
         * 其中两点不能是同一个点，x1不等于x
         *
         * 由于存在数学精度问题，需要把上述表达式的比较，转换为对分子和分母分别比较，比较之前需要将分子分母约分到最简
         * 进而就要求分子和父母的最大公约数
         */
        fun isOnTheLine(x: Int, y: Int): Boolean {
            if (x == x1 && y == y1 || x == x2 && y == y2) return true
            val d1 = greatestCommonDivisor(y2 - y1, x2 - x1)
            val d2 = greatestCommonDivisor(y - y1, x - x1)
            val isSameNumerator = (y2 - y1) / d1 == (y - y1) / d2
            val isSameDenominator = (x2 - x1) / d1 == (x - x1) / d2
            return isSameNumerator && isSameDenominator
        }

        /**
         * 求[a]和[b]的最大公约数
         * 使用辗转相除法
         */
        private fun greatestCommonDivisor(a: Int, b: Int): Int {
            if (a == b) return a
            var big = if (a > b) a else b
            var small = if (a < b) a else b
            while (small != 0) {
                val remainder = big % small
                big = small
                small = remainder
            }
            return big
        }
    }
}

复杂度

  • 时间复杂度O(n^3)
  • 空间复杂度O(1)