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

ernest.wang 发布于2019-08-14 12:49 / 2723人阅读

摘要：哈希表复杂度时间空间思路一个点加一个斜率，就可以唯一的确定一条直线。这里，我们用哈希表，以斜率为，记录有多少重复直线。注意哈希表的为，但是可以有正和负的，而且不一样。

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)

思路

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

注意

哈希表的Key为Double，但Double是可以有正0和负0的，而且不一样。所以我们要用if(slope * slope == 0) slope = 0;把负0都变成正0

代码

public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length <= 1) return points.length;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < points.length; i++){
            //过当前点的直线组成的哈希表，斜率为key
            HashMap lines = new HashMap();
            int vertical = 0, same = 1, currMax = 0;
            for(int j = i + 1; j < points.length; j++){
                // 统计相同的点
                if(points[i].x == points[j].x && points[i].y == points[j].y){
                    same++;
                    continue;
                }
                // 统计斜率为无穷的点，他们都在一条直线上
                if(points[i].x == points[j].x){
                    vertical++;
                    continue;
                }
                // 计算连线的斜率
                double slope = ((double)points[i].y - (double)points[j].y) / ((double)points[i].x - (double)points[j].x);
                // 修正负0
                if(slope * slope == 0) slope = 0;
                lines.put(slope, lines.containsKey(slope) ? lines.get(slope) + 1 : 1);
                currMax = Math.max(currMax, lines.get(slope)); 
            }
            // 经过该点的直线上最多的点数，我们在无穷斜率和正常斜率中选较大的，还要加上相同的点数
            currMax = Math.max(vertical, currMax) + same;
            max = Math.max(currMax, max);
        }
        return max;
    }
}

云服务器 GPU云服务器 Points LeetCode LeetCode_String leetcode_35_SearchIn

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

转载请注明本文地址：https://www.ucloud.cn/yun/64724.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 s...

张宪坤 2019-08-14 14:05 评论0 收藏0
[LintCode] Max Points on a Line

摘要：两次循环对中第个和第个进行比较设置重复点数，相同斜率点数。内部循环每次结束后更新和点相同斜率的点的最大数目。外部循环每次更新为之前结果和本次循环所得的较大值。重点一以一个点为参照求其他点连线的斜率，不需要计算斜率。 Problem Given n points on a 2D plane, find the maximum number of points that lie on th...

bingo 2019-08-14 15:14 评论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
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