[LeetCode] 149. Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

直线上最多的点数。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-points-on-a-line
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道数学题。暴力解不难想，难的是如何优化。

我们知道，两点确定一条直线，也就有了这条直线的斜率 slope。暴力解的做法是三层 for 循环。用第一层 for 循环找到第一个点，用第二层 for 循环找到第二个点，再用第三层 for 循环找到第三个点，比较点一 - 点二和点二 - 点三的斜率是否一样。

时间O(n^3)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxPoints(int[][] points) {
 3         int len = points.length;
 4         int res = 1;
 5         for (int i = 0; i < len; i++) {
 6             int[] first = points[i];
 7             for (int j = i + 1; j < len; j++) {
 8                 int[] second = points[j];
 9                 int count = 2;
10                 for (int k = j + 1; k < len; k++) {
11                     int[] third = points[k];
12                     int slope1 = (second[1] - first[1]) * (third[0] - second[0]);
13                     int slope2 = (third[1] - second[1]) * (second[0] - first[0]);
14                     if (slope1 == slope2) {
15                         count++;
16                     }
17                 }
18                 res = Math.max(res, count);
19             }
20         }
21         return res;
22     }
23 }

优化的思路如下。我们需要一个 hashset 排除重复的点，对于每一个点 a 而言，我们还需要一个 hashmap<斜率，次数> 记录每个穿过点 a 的直线的斜率分别出现了几次。与其是把所有的点两两遍历然后两两求斜率，这个思路的做法其实找的是全局范围内的 unique 的斜率值，然后看哪个斜率值出现的次数最多。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public int maxPoints(int[][] points) {
 3         int len = points.length;
 4         // corner case
 5         if (len < 2) {
 6             return len;
 7         }
 8         
 9         // normal case
10         HashSet<String> set = new HashSet<>();
11         int res = 1;
12         // for循环遍历的是第一个点
13         for (int i = 0; i < len && !set.contains(points[i][0] + "-" + points[i][1]); i++) {
14             int[] a = points[i];
15             // 和当前点一样的点有多少
16             int same = 0;
17             HashMap<Double, Integer> map = new HashMap<>();
18             int max = 1;
19             for (int j = i + 1; j < len; j++) {
20                 if (isSame(a, points[j])) {
21                     same++;
22                 }
23                 // 穿过当前点的直线的斜率
24                 double slope = getSlope(a, points[j]);
25                 map.put(slope, map.getOrDefault(slope, 1) + 1);
26                 max = Math.max(max, map.get(slope));
27             }
28             // 记录当前点，这样以后即使遇到重复的点，也不会把他作为第一个点再扫描
29             set.add(a[0] + "-" + a[1]);
30             res = Math.max(res, max + same);
31         }
32         return res;
33     }
34     
35     private boolean isSame(int[] a, int[] b) {
36         return a[0] == b[0] && a[1] == b[1];
37     }
38     
39     private double getSlope(int[] a, int[] b) {
40         if (a[0] == b[0]) return Double.MAX_VALUE;
41         if (a[1] == b[1]) return 0;
42         return ((double) b[0] - a[0]) / ((double) b[1] - a[1]);
43     }
44 }

LeetCode 题目总结