LeetCode 149 Max Points on a Line

Begin

Description:

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

题目理解：

首先这道题的题干很短，基本第一遍都会理解错，也不清楚输入是个啥，所以这道题被踩了300多次，赞了100次不到…

经过几次错误的理解之后，明白了题目的意思：给一系列点，每个点有一个（x，y）的坐标取值，找出处于同一条直线上的最多点数。

这里需要注意：

• 可以有取值重复的坐标点。
• 直线可以是任意的斜率（以x,y的直角坐标系来看）。

思路

思路一：

计算出可能的所有直线，统计每一条直线上的点的个数。直线以它的斜率加截距来表示：

$$y = kx + b$$

给予两个点的坐标，$(x_1,y_1)$、$(x_2,y_2)$，计算$k$与$b$的计算公式为：

$$k = \frac{y_1 - y_2}{x_1 - x_2}$$ $$b = y_1 - k x_1$$

遇到的问题：

1. 除法会有精度损失，可能造成不一样的直线算出来的斜率一样，而且可能会溢出，因为有加减运算。
2. 不好统计直线上的点数，例如A、B、C三个点在一条线上，那么就有(A,B)(B,C)(A,C)三个组合， 那么这条直线上的点数该如何统计？

思路二：

以每一个点为起点，计算它与其它的点组成的直线，统计直线上的点的次数。

这里的直线斜率直接使用分数表示，不需要截距，因为起点为同一个点。

这里的分数表示需要计算分子与分母的最大公约数，在后面进行介绍，感觉这个才是这道题的重点。

代码

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    
    private class PCount {
        Point point;
        int count = 1;
        public PCount(Point point) {
            this.point = point;
        }
    }
    
    private int GCD(int a, int b) {
        int c;
        while ( b != 0 ) { 
            c = a % b; 
            a = b;  
            b = c;
        }
        return a;
    }
    
    public int maxPoints(Point[] points) {
        if ( points == null )
            return 0;
        int max = 0;
        PCount[] pcount = new PCount[points.length];
        int pidx = 0;
        Map<String, Integer> ptable = new HashMap<>();
        for ( Point point : points ) {
            String coord = point.x + "*" + point.y;
            Integer idx = ptable.get(coord);
            if ( idx == null ) {
                ptable.put(coord, pidx);
                pcount[pidx++] = new PCount(point);
            } else
                pcount[idx].count++;
        }
        if ( pidx == 1 )
            return points.length;
        for ( int i = 0; i < pidx; i++ ) {
            Point p1 = pcount[i].point;
            Map<String, Integer> lines = new HashMap<>();
            for ( int j = i + 1; j < pidx; j++ ) {
                Point p2 = pcount[j].point;
                String line = null;
                if ( p1.x == p2.x ) {
                    line = "1/0";
                } else if ( p1.y == p2.y ) {
                    line = "0/1";
                } else {
                    int denominator = p1.y - p2.y;
                    int numerator = p1.x - p2.x;
                    int gcd = GCD(denominator, numerator);
                    if ( gcd != 0 ) {
                        denominator /= gcd;
                        numerator /= gcd;
                    }
                    line = denominator + "/" + numerator;
                }
                lines.put(line, lines.getOrDefault(line, pcount[i].count) + pcount[j].count);
            }
            for ( int count : lines.values() ) 
                max = max < count ? count : max;
        }
        return max;
    }
}

最大公约数

对于两个数A、B，求解它们的最大公约数。

方法一：

选出A、B中最小的数，向下一个一个进行取余，直到两个数的余数同时为0：

public int GCD(int a, int b) {
    int c = a > b ? b : a;
    while ( a % c != 0 || b % c != 0 ) {
        c--;
    }
    return c;
}

方法二：

显然方法一的效率很低，那么肯定有别的快速的方法。

对A、B，假设它们的最大公约数为C，那么：

$$A = k_1 C$$ $$B = k_2 C$$

注意，其中$k_1$与$k_2$一定是互质的，那么对A与B取余：

$$D = A \% B = (k_1 \% k_2)C$$

那么注意到D的取值情况：

1. D的值为0，那么B就是最大公约数，其中$k_2=1$。
2. D的值不为0，D与B之间的最大公约数还是C。

由于D的绝对值会比A要小，并且B、D之间的最大公约数还是C，所以可以计算B、D之间的最大公约数来代替计算A、B之间的。

public int GCD(int a, int b) {
    int c;
    while ( b != 0 ) { 
        c = a % b; 
        a = b;  
        b = c;
    }
    return a;
}

这个方法会比方法一快很多。