文档章节

149. Max Points on a Line

cofama
 cofama
发布于 2017/05/07 23:11
字数 748
阅读 3
收藏 0

原题链接

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

注意题目中给的点有可能是重复的。要统计哪条直线上的点最多,就一定要计算每两个点之间的直线,这是不可避免的,所以时间复杂度至少为O(n^2)。采用遍历的方法,当遍历第i个点时,只需计算它与第i+1个及之后的点的直线,这样避免了重复计算。

我最初的想法是用y=kx+b表示直线方程,然后记录每个(k,b)组合出现的次数,出现最多的那个组合表示的直线方程就是经过点最多的。出现次数可以用map<pair<double,double>, int>类型记录。这个方法有两个问题:第一,k表示斜率,但不是每两个点间的直线斜率都存在,所有垂直于x轴的直线都没有斜率,所以可能会出现被0除的错误;第二,题目给出的点坐标都是整数,计算k时会出现精度丢失的问题,可能出现两条斜率相近的直线被误认为相同的情况。

因为k=(y2-y1)/(x2-x1),为了解决上述两个问题,我不用k表示直线,而是直接用dy=y2-y1和dx=x2-x1表示。但是这样就要用dy、dx、b三个参数表示方程了,不能用map<pair, int>的数据结构了。b=y-kx,是由直线上的一个点和斜率决定的。如果我们在遍历每一个点时,都新建一个map记录每个(dy,dx)组合出现的次数,就可以省略b了,因为每条直线都会经过当前遍历的点,所以只要直线的dy、dx相同,它们的b值也必定相同。这样,在每个点遍历结束时,选出经过当前点的直线中包含点最多的那条,最后再在所有点的最值中选出包含点最多的直线。

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        int nums = points.size();
        int x,y,gcd,duplicate;
        pair<int, int> p;
        int maxslope, maxline=0;
        
        for(int i=0; i<nums; i++) {
            duplicate = 1;
            maxslope = 0;
            map<pair<int,int>, int> count;
            for(int j=i+1; j<nums; j++) {
                y = points[j].y-points[i].y;
                x = points[j].x-points[i].x;
                if(x==0&&y==0) {
                    duplicate++;
                }
                else {
                    gcd = GCD(x,y);
                    x = x/gcd;
                    y = y/gcd;
                    p.first = x;
                    p.second = y;
                    count[p]++;
                    maxslope = max(maxslope, count[p]);
                }
            }
            maxline=max(maxline, maxslope+duplicate);
        }
        return maxline;
    }

 private:   
    int GCD(int a, int b) {
        if(b==0) return a;
        else return GCD(b, a%b);
    }
};

注意dx、dy(代码中的x、y)需要先用它们的最大公约数去除,再去map中查找。因为例如(1,1)、(2,2)、(3,3)三个点在同一直线上,(1,1)、(2,2)计算出的(dx,dy)是(1,1),(1,1)、(3,3)计算出的(dx,dy)是(2,2),如果不进行约分,就会认为这两条直线是不同的。

© 著作权归作者所有

cofama
粉丝 0
博文 24
码字总数 19162
作品 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. 题意:给一个二维平面,上面有好多点,有横纵坐标,找出一条直线,使得这条线上的点...

努力的C
2017/10/19
0
0
使用Oracle的DBMS_SQL包执行动态SQL语句

引用自:http://blog.csdn.net/ggjjzhzz/archive/2005/10/17/507880.aspx 在某些场合下,存储过程或触发器里的SQL语句需要动态生成。Oracle的DBMSSQL包可以用来执行动态SQL语句。本文通过一个...

jimbuster
2007/09/26
0
0
Codeforces I. Barcelonian Distance

题目描述: In this problem we consider a very simplified model of Barcelona city. Barcelona can be represented as a plane with streets of kind x=cx=c and y=cy=c for every intege......

小张人
07/20
0
0
alibaba.druid.sql.parser.ParserException: unclosed str. pos 92, line 1, column 93, token RPAREN

RonganSchedulerWorker-3] ERROR c.a.d.f.s.StatFilter - [mergeSql,149] - merge sql error, dbType mysql, druid-1.1.14, sql : SELECT MAX(t.`maxtime`) FROM t_rsd_datax_subjob t WHERE......

ios应用猫
09/04
27
0
mysql配置文件不生效以及配置同步复制报错“The server is not configured as slave”解决办法

今晚给2台mysql数据库配置主从同步,因为驾轻就熟,所以很快就配置到最后一步了,谁知道执行最后一个命令“slave start”时给我来了个报错“ERROR 1200 (HY000): The server is not configu...

初级泥水工
2014/05/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

web前端开发高级

前端高效开发框架技术与应用 Vue 基础 Vue 框架简介 MVX 模式介绍 Vue 框架概述 如何使用 Vue.js 基础语法 实例对象 生命周期 模板语法 计算属性 Methods 方法 渲染 列表渲染 条件渲染 事件与...

达达前端小酒馆
44分钟前
6
0
PostgreSQL 11.3 locking

rudi
今天
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
21
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
5
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部