文档章节

在二维平面上,有一些点,请找出经过点数最多的那条线。

一贱书生
 一贱书生
发布于 2016/11/19 13:46
字数 520
阅读 166
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

/**

 * 功能:在二维平面上,有一些点,请找出经过点数最多的那条线。[java] view plain copy

 

  1. /** 
  2.      * 思路:在任意两点之间画一条无线长的直线,用散列表追踪那条直线出现的次数最多。时间复杂度O(N*N) 
  3.      * 注意: 
  4.      *      1)用斜率和y轴截距来确定是否是同一条直线。 
  5.      *      2)浮点数不一定能用二进制数准确表示,因此检查两个浮点数的差值是否在某个极小值(epsilon)内。 
  6.      *      3)对于散列表而言,斜率相等,未必散列值相同。因此,将斜率减去一个极小值,并以得到的结果flooredSlope作为散列键。 
  7.      *      4)取得所有可能相等的直线,搜索三个位置:flooredSlope,flooredSlope-epsilon,flooredSlope+epsilon。 
  8.      * @param points 
  9.      * @return 
  10.      */  
  11.     public static MyLine1 findBestLine(GraphPoint[] points){  
  12.         MyLine1 bestLine=null;  
  13.         int bestCount=0;  
  14.           
  15.         HashMap<Double,ArrayList<MyLine1>> lineBySlope=new HashMap<Double, ArrayList<MyLine1>>();  
  16.           
  17.         for(int i=0;i<points.length-1;i++){  
  18.             for(int j=i+1;j<points.length;j++){  
  19.                 MyLine1 line=new MyLine1(points[i],points[j]);  
  20.                 insertLine(lineBySlope,line);  
  21.                 int count=countEquivalentLines(lineBySlope,line);  
  22.                 if(count>bestCount){  
  23.                     bestCount=count;  
  24.                     bestLine=line;  
  25.                 }  
  26.             }  
  27.         }  
  28.         return bestLine;  
  29.           
  30.     }  
  31.   
  32.     private static int countEquivalentLines(HashMap<Double, ArrayList<MyLine1>> lineBySlope, MyLine1 line) {  
  33.         double key=line.floorToNearestEpsilon(line.slope);  
  34.         double eps=line.epsilon;  
  35.         int count=countEquivalentLines(lineBySlope.get(key), line)+countEquivalentLines(lineBySlope.get(key-eps), line)+  
  36.                 countEquivalentLines(lineBySlope.get(key+eps), line);  
  37.           
  38.         return count;  
  39.     }  
  40.       
  41.     public static int countEquivalentLines(ArrayList<MyLine1> lines,MyLine1 line){  
  42.         if(lines==null)  
  43.             return 0;  
  44.         int count=0;  
  45.         for(MyLine1 paralleLine:lines){  
  46.             if(paralleLine==line)  
  47.                 count++;  
  48.         }  
  49.         return count;  
  50.     }  
  51.   
  52.     private static void insertLine(HashMap<Double, ArrayList<MyLine1>> lineBySlope, MyLine1 line) {  
  53.         ArrayList<MyLine1> lines=null;  
  54.         double key=line.floorToNearestEpsilon(line.slope);  
  55.         if(!lineBySlope.containsKey(key)){  
  56.             lines=new ArrayList<MyLine1>();  
  57.             lineBySlope.put(key, lines);  
  58.         }else{  
  59.             lines=lineBySlope.get(key);  
  60.         }  
  61.         lines.add(line);//注意此处添加的用法  
  62.     }  
  63.       
  64.       
  65.   
  66. class MyLine1{  
  67.     public static double epsilon=0.0001;  
  68.     public double slope,intercept;  
  69.     public boolean infiniteSlope=false;  
  70.       
  71.     public MyLine1(GraphPoint p,GraphPoint q){  
  72.         if(Math.abs(p.x-q.x)>epsilon){//两个点的x坐标不同  
  73.             slope=(p.y-q.y)/(p.x-q.x);//斜率  
  74.             intercept=p.y-slope*p.x;//y轴截距  
  75.         }else{  
  76.             infiniteSlope=true;  
  77.             intercept=p.x;//x轴截距  
  78.         }  
  79.     }  
  80.       
  81.     public double floorToNearestEpsilon(double d){  
  82.         int r=(int) (d/epsilon);//使原d保留小数位后的4位(epsilon=0.0001)  
  83.         return ((double)r)*epsilon;  
  84.     }  
  85.       
  86.     public boolean isEquivalent(MyLine1 line){  
  87.         if((slope==line.slope)&&(intercept==line.intercept)&&(infiniteSlope==line.infiniteSlope))  
  88.             return true;  
  89.         return false;  
  90.     }  
  91.       
  92.     public boolean isEquivalent(double a,double b){  
  93.         return Math.abs(a-b)<epsilon;  
  94.     }  
  95.       
  96.   
  97.       
  98. }  
  99.   
  100. class GraphPoint{  
  101.     int x;  
  102.     int y;  
  103.       
  104.     public GraphPoint(int x,int y){  
  105.         this.x=x;  
  106.         this.y=y;  
  107.     }  

 

一贱书生
粉丝 20
博文 723
码字总数 600123
作品 0
私信 提问
加载中
请先登录后再评论。
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
3.9K
3
我的架构演化笔记 功能1: 基本的用户注册

“咚咚”,一阵急促的敲门声, 我从睡梦中惊醒,我靠,这才几点,谁这么早, 开门一看,原来我的小表弟放暑假了,来南京玩,顺便说跟我后面学习一个网站是怎么做出来的。 于是有了下面的一段...

强子哥哥
2014/05/31
976
3
【opencv】图形的绘制

1.矩形图像的绘制: 原函数:void cvRectangle(CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8,int shift=0) img就是需要绘制的图像 pt1 and pt......

其实我是兔子
2014/10/08
1.1K
1
Nutch学习笔记4-Nutch 1.7 的 索引篇 ElasticSearch

上一篇讲解了爬取和分析的流程,很重要的收获就是: 解析过程中,会根据页面的ContentType获得一系列的注册解析器, 依次调用每个解析器,当其中一个解析成功后就返回,否则继续执行下一个解...

强子哥哥
2014/06/26
712
0
游戏引擎--DarkGDK

Dark游戏开发工具包是一个完整的游戏引擎技术利用最新DirectX 9.0。 微软公司制作的编游戏的链接库工具,专门配合Visual C++ 2008 Express 和 DirextX 9.0 SDK,可以编辑制作3D,2D游戏,制作...

匿名
2013/04/01
2.2K
0

没有更多内容

加载失败,请刷新页面

加载更多

Smartbi数据分析工具处理大数据性能如何?

为什么需要跨库整合能力 Smartbi支持多种数据源轻松接入,基本涵盖了市面上所有主流的数据库。无可否认多元的数据连接能力使Smartbi能快速连接现有数据源,构建统一的数据分析平台。但在项目...

osc_w0uxg75l
19分钟前
0
0
深入Vue 底层原理以及运行机制

Vue,React 这样的框架可以说是现在前端的必备技能,一个刚入门两三个月的前端都是要会Vue的,而且随着Vue3.0发布日程的推进,使用的人群变得多了,开始想去了解它。 Vue这么受大众接受,那么...

五月君
今天
0
0
好用的Excel大数据分析工具

为什么需要Excel分析 自助BI使得BI不再是高管领导的专利,促成了BI的平民化,更是BI的发展趋势。但自助BI工具的选择却并不简单,很多厂商推出了自己的自助分析工具,但在企业的使用过程中,实...

osc_vuza8uho
19分钟前
6
0
企业玩转DevOps转型:由弱到强,只需7步

【摘要】 在参考业界方法并总结客户成功故事的基础上,本文提出了“七步法”路线图,希望能帮助更多的企业顺利进行DevOps转型。 从2009年诞生,DevOps已经悄然走过了10多个年头。Gartner在技...

华为云开发者社区
20分钟前
0
0
浙江日报丨AI赋能,如何抢占“智”高点

  今天在杭州市余杭区秒优服饰智能工厂,机器人将订单所需的面料辅料精准送到各个吊挂生产线,每台机器、每个工人的具体任务、实时进度等都化为大数据,显示在工厂的大屏幕上。作为一家今年...

osc_wfvuuuju
21分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部