聖地亞歌

Leetcode P0149"Max Points on a Line" 题解

2020/09/17 Leetcode

博文中会简要介绍Leetcode P0149题目分析及解题思路。

“Max Points on a Line”这道题看起来难，其实就是纯数学问题，最简单的思路就是每个点求出一条线，然后判断其他点是否在这条线上，接着记录所有在这条线上的点，最后和当前最大记录值比较即可。这样的解法的时间复杂度是O(n^3)。

其实也有O(n^2)的解法，可以将所有截距和斜率当作键存储在HashTable中，这样相同斜率和截距就会被统计到该键对应的值中。不过本文不会详细讲解这个方法，有兴趣的话大家可以去Leetcode官网上查看。

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6
Plaintext

这道题由于涉及除法精度问题，建议使用点斜式而不是截距式，思路如下，

    首先我们可以得到下式，
    y1 = k x1 + C = [(y1 - y2) / (x1 - x2)] x1 + C
    
    上述是传统的截距式写法，然后我们可以等式两边同时乘上分母来避免除法，
    y1 (x1 - x2) - x1 (y1 - y2) = C (x1 - x2)

    
    令dX=x1-x2、dY=y1-y2并且C*dX=CX，那么dX、dY和CX都可以通过两点计算出来，即可以得到下式，
    y1 dX - x1 dY = C dX = CX

    然后扫一遍其他的点，最终只需要判断下式即可
    y3 dX - x3 dY = CX
Plaintext

以下是Java的题解代码实现。

class Solution {
    public int maxPoints(int[][] points) {
        // 少于三个点则不用判断
        int len = points.length;
        if (len < 3) {
            return len;
        }

        int max = 0;
        for (int i = 0; i < len - 1; ++i) {
            for (int j = i + 1; j < len; ++j) {
                // points[i] 和 points[j]
                // 这里需要一个bool值的slope 来判断斜率是否存在，不存在的话设置为false,后续单独处理
                boolean slope = true;
                long dX = points[i][0] - points[j][0];
                long dY = points[i][1] - points[j][1];
                long interceptDX = 0;
                if (dX == 0) {
                    // 这时候两个点连线是垂直于x轴的，木有斜率
                    slope = false;
                } else {
                    // 这个是点斜式的变形， 等式左侧是(截距*dx),自己在演算纸上验算一下吧,就不详细说了
                    interceptDX = dX * points[i][1] - dY * points[i][0];
                }

                int count = 0;
                for (int k = 0; k < len; ++k) {
                    if (slope) {
                        // 将k点的x和y带入看直线方程是否有解。
                        if (interceptDX == dX * points[k][1] - dY * points[k][0]) {
                            ++count;
                        }
                    } else {
                        if (points[k][0] == points[i][0]) {
                            ++count;
                        }
                    }
                }
                max = Math.max(max, count);
            }
        }

        return max;
    }
}
Java

除了上述的点斜式三点共线的方法判断以外，还可以使用叉积法判断三点共线。C++代码实现了叉积法的解法。

以下是C++的题解代码实现。

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int res = 0, n = points.size();
        for (int i = 0; i < n; ++i) {
            int duplicate = 1;
            for (int j = i + 1; j < n; ++j) {
                int cnt = 0;
                long x1 = points[i][0], y1 = points[i][1];
                long x2 = points[j][0], y2 = points[j][1];
                if (x1 == x2 && y1 == y2) {++duplicate;continue;}
                for (int k = 0; k < n; ++k) {
                    int x3 = points[k][0], y3 = points[k][1];
                    if (x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1 * y3 == 0) {
                        ++cnt;
                    }
                }
                res = max(res, cnt);
            }
            res = max(res, duplicate);
        }
        return res;
    }
};
C++

Search