[LintCode] Max Points on a Line

bingo 发布于2019-08-14 15:14 / 1387人阅读

摘要：两次循环对中第个和第个进行比较设置重复点数，相同斜率点数。内部循环每次结束后更新和点相同斜率的点的最大数目。外部循环每次更新为之前结果和本次循环所得的较大值。重点一以一个点为参照求其他点连线的斜率，不需要计算斜率。

Problem

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

Example

Given 4 points: (1,2), (3,6), (0,0), (1,3).
The maximum number is 3.

Note

建立一个斜率对应point个数的HashMap。
两次循环对points中第i个和第j个进行比较：
设置重复点数duplicate，相同斜率点数count。内部循环每次结束后更新count——和点i相同斜率的点的最大数目。（点i可能有很多相同斜率点的集合，故内层遍历完之后取最大的集合的大小。）
外部循环每次更新res为之前结果和本次循环所得duplicate+count的较大值。
重点一：以一个点为参照求其他点连线的斜率，不需要计算斜率。
重点二：两次循环体现重点一中的相对关系，可以让j从i开始，节省时间。

Solution

public class Solution {
    public int maxPoints(Point[] points) {
        // Write your code here
        int res = 0;
        if (points == null || points.length == 0) {
            return 0;
        }
        for (int i = 0; i < points.length; i++) {
            int count = 0;
            int duplicate = 1;
            Map map = new HashMap();
            Point p = points[i];
            for (int j = i; j < points.length; j++) {
                Point q = points[j];
                if (q == p) continue;
                if (q.x == p.x && q.y == p.y) duplicate++;
                else {
                    double s = p.x == q.x ? Double.MAX_VALUE: (double)(p.y-q.y)/(p.x-q.x);
                    map.put(s, map.containsKey(s) ? map.get(s)+1: 1);
                    count = Math.max(count, map.get(s));
                }
            }
            res = Math.max(res, count+duplicate);
        }
        return res;
    }
}

GPU云服务器云服务器 Points LintCode LintCode134_LRU line

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

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

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] 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] 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] Baseball Game

Problem Youre now a baseball game point recorder. Given a list of strings, each string can be one of the 4 following types: Integer (one rounds score): Directly represents the number of points you get...

newtrek 2019-08-16 12:36 评论0 收藏0