[Leetcode] Max Points on a Line 直线上最多的点数

张宪坤发布于2019-08-14 14:05 / 517人阅读

摘要：分子分母同时除以他们的最大公约数即可得到最简分数，一般求的是两个正整数的。这道题和有可能是，分别表示与轴或轴平行的斜率注意不能同时为表示同一个点没有意义，所以这道题我们规定取值范围。

Max Points on a Line

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

哈希表法 复杂度

O(N^2) 时间 O(N) 空间， N为点数

思路

应知应会：

平面里确定一条直线要两个数据，可以是两个不同的点(高中数学做法)，也可以是一个点加一个斜率(这道题做法)

斜率k = (y2 - y1)/(x2 - x1)，当 x1 == x2 时，分母为0，斜率为无穷，表示和y轴平行的直线们

在计算机里使用double表示斜率，是不严谨的也是不正确的，double有精度误差，double是有限的，斜率是无限的，无法使用有限的double表示无限的斜率，不过此题的test case没有涉及这个问题

表示斜率最靠谱的方式是用最简分数，即分子分母都无法再约分了。分子分母同时除以他们的最大公约数gcd即可得到最简分数

gcd(a,b)，一般求的是两个正整数的gcd。这道题a和b有可能是0，分别表示与x轴或y轴平行的斜率(注意ab不能同时为0,表示同一个点没有意义)，所以这道题我们规定ab取值范围：a>=0,b>=0。至于负数，先变成正数取gcd，再确定最终斜率的正负

gcd ( a , b ) = (b == 0) ? a : gcd ( b , a % b ), a,b是任意非负整数且a,b至少有一个不为0

观察gcd(a,b)，假设a,b为非负整数：

a和b中有一个为零，那么gcd为另一个不为0的数；

a和b都为0，gcd为0；

算法：

没什么算法就是穷举：
对每个点，都计算一下该点和其他点连线的斜率，这样对于这个点来说，相同斜率的直线有多少条，就意味着有多少个点在同一条直线上，因为这些直线是相同的。另外，如果计算过点A和点B的直线，当算到点B时，就不用再和A连线了，因为AB这条直线上的点数已经都计算过了。这里，我们用哈希表，以斜率为key，记录有多少重复直线。

注意

求gcd的utility:

public int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

两层循环外层 i 从 0 到 n, 内层 j 从 i+1 到 n

如果想要自定义Slope(斜率)类作为HashMap的Key的话要重写hashCode()和equals()函数，偷懒的话可以把斜率的分数表示成String作为Key，这样就省了一些事

hashmap的value的含义应定义为：过cur点以key为斜率的直线有几个除了cur以外的点。在算完过cur的所有直线后，统计cur点的总个数howManyCur，加到当前点最多的直线上，即可得到含cur点的最大直线上的点数

代码

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length <= 1)
            return points.length;
        int maxUniv = Integer.MIN_VALUE;
        for (int i = 0; i < points.length; i++) {
            Point cur = points[i];
            HashMap map = new HashMap();
            int howManyCur = 1, maxLocal = 0;
            for (int j = i + 1; j < points.length; j++) {   //这里可以从i+1开始，之前的都算过了
                    Point iter = points[j];
                    if (iter.x == cur.x && iter.y == cur.y) {//同一顶点
                        howManyCur += 1;
                    } 
                    else {          //不同顶点
                        String key = getSlopeInString(cur, iter);
                        //map里存(过cur点,斜率key)代表的直线有多少除了cur的点
                        map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
                        maxLocal = Math.max(maxLocal, map.get(key));
                    }
            }
            maxLocal = howManyCur + maxLocal;
            maxUniv = Math.max(maxLocal, maxUniv);
        }
        return maxUniv;
    }
    public String getSlopeInString(Point cur, Point iter) {
        int numerator = iter.y - cur.y;
        int denominator = iter.x - cur.x;
        String sign = getSign(numerator, denominator);
        int gcd = gcd(Math.abs(numerator), Math.abs(denominator));//0和任意一个非零数"a"的gcd为"a",0和0的gcd为0,所以斜率为无穷的情况分母为0
        return sign + Math.abs(numerator)/gcd + "/" + Math.abs(denominator)/gcd;
    }
    //a和b为非负整数 且 a和b不同时为0
    public int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
    public String getSign(int a, int b) {
        if (a <= 0 && b <= 0 || a >= 0 && b >= 0)
            return "+";
        else 
            return "-";
    }
}

云服务器 GPU云服务器观看人数最多的av网站使用最多的编程语言服务器最多的公司排名国内云服务器最多的公司

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64800.html

[Leetcode] Max Points on a Line 线上最大点数

摘要：哈希表复杂度时间空间思路一个点加一个斜率，就可以唯一的确定一条直线。这里，我们用哈希表，以斜率为，记录有多少重复直线。注意哈希表的为，但是可以有正和负的，而且不一样。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same stra...

ernest.wang 2019-08-14 12:49 评论0 收藏0
LeetCode 4

摘要：这个题的思路就是找数组里的两个点，用这两个点来做一条直线，然后看数组里的点都在直线上不，我用的是两点式，需要考虑两个点或坐标相同的特殊情况。 Max Points on a Line https://oj.leetcode.com/problems/max-points-on-a-line/ Given n points on a 2D plane, find the maximu...

zhkai 2019-08-14 11:46 评论0 收藏0
Leetcode 356. Line Reflection

摘要：题目解法这道题主要是判断个点是否沿某条线对称，可以从提示看出来所有的点应该要满足所以先把所有的点扫一遍存下来，找到和然后再扫一遍，判定是否点都是延直线对称的。时间复杂度空间复杂度代码题目： Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the gi...

ivyzhang 2019-08-14 16:59 评论0 收藏0
leetcode-149-Max Points on a Line

Given n points on a 2D plane,find the maximum number of points that lie on the same straight line. from decimal import Decimal # Definition for a point. class Point: def __init__(self, a=0, b=0)...

darcrand 2019-07-31 11:03 评论0 收藏0