LeetCode149-直线上最多的点数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/max-points-on-a-line/

中文链接：https://leetcode-cn.com/problems/max-points-on-a-line/

题目详述

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

示例 1:

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

示例 2:

1
2
3
4
5
6
7
8
9
10
11
输入: [[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

题目详解

  • 先枚举一个定点，然后将其它点按斜率分组，斜率指与定点连线的斜率，分组可以利用哈希表。
    由于一个定点加斜率可以唯一确定一条直线，所以被分到同一组的点都在一条直线上。组中点数的最大值就是答案。
  • 上述做法存在的一些问题：
    • 由于斜率是一个浮点数，可能存在精度问题。
    • 竖直直线斜率不存在，需要单独处理。
    • 与定点重合的点可以被分到所有组中，需要单独处理。
  • 为了简化问题，我们可以换一种方式表示斜率，用它的最简分数（除以 gcd 之后的值）来表示斜率，这样可以解决浮点数精度问题，并且可以解决斜率不存在的表示问题。定义一个 Slope 类来表示这个最简分数。
  • 时间复杂度为 O(n^2)。
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
public class LeetCode_00149 {

    public int maxPoints(int[][] points) {
        int n = points.length;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            Map<Slope, Integer> map = new HashMap<>();
            // 同一直线上的点的个数（不包含坐标相同的点，坐标相同的点单独计算）
            int duplicates = 0;
            for (int j = i + 1; j < n; ++j) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0 && y == 0) {
                    ++duplicates;
                } else {
                    int g = gcd(x, y);
                    Slope slope = new Slope(x / g, y / g);
                    map.put(slope, map.getOrDefault(slope, 1) + 1);
                }
            }
            // 用与定点重合的点的个数更新最大值
            res = Math.max(res, duplicates + 1);
            res = Math.max(res, map.values().stream().max(Integer::compareTo).orElse(0) + duplicates);
        }
        return res;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    class Slope {
        int x, y;

        public Slope(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Slope slope = (Slope) o;

            if (x != slope.x) return false;
            return y == slope.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }
}