`
huntfor
  • 浏览: 201076 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[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 straight line.

坐标轴上面有n个点,求共线的最大点数。

这道题是leetcode上通过率最低的,但是绝对不是最难的,几点共线我们可以根据y = k x + b算出:

1. 平行于y轴的垂线斜率设为最大值,平行于x轴的线与普通斜线没啥区别,不需要做特殊处理;

2. 比较棘手的是重复点

这道题,我重构了一个数据结构,包含了k,b从而确定了每一条线,二重遍历坐标轴中每一个点(时间复杂度为n*n)从而遍历了图中的每一条线,但是当遇到重合点的时候,不知道该如何下手了。

后来查到了这样的算法,压根就不需要关心斜率,对每个点进行雷达式的扫描处理,简直碉堡。

其算法思想是这样的:

1. 对每个点p进行循环扫描(扫描坐标中所有的点),并维护一个duplicate变量,初值为1,表示自己。

2. 扫描到点q时,计算直线pq的斜率k,这时b就不需要关心了,原因自己画图,想一下就不难知道。

2.1 当p点与q点重合时,duplicate++

2.2 计算斜率(边界case,斜率为∞),记录斜率为k的直线个数

3. 对坐标中所有的点处理完之后,遍历map中的value + duplicate的最大值,有一种特殊情况:所有的点都是重合点,map为空。

 

代码如下:

	public int maxPoints(Point[] points) {
		if(points== null) return 0;
		if(points.length <= 2) return points.length;
		int max = 0;
		int duplicate = 1;//this field setting is amazing
		Map<Double,Integer> map = new HashMap<Double,Integer>();
		for(int i = 0; i < points.length; i++){
			map.clear();
			duplicate = 1;
			Point p = points[i];
			for(int j = 0 ; j < points.length; j++){
				if(i == j) continue;
				Point tem = points[j];
				double slope = 0.0;
				if(tem.x == p.x && tem.y == p.y){
					duplicate ++;
					continue;
				}else if(tem.x == p.x){
					slope = Integer.MAX_VALUE;
				}else{
					slope = tem.y == p.y ? 0 : 1.0 * (tem.y - p.y) / (tem.x - p.x);
				}
				map.put(slope, map.containsKey(slope) ? map.get(slope) + 1 : 1 );
			}
			if(map.keySet().size() == 0){
				max = duplicate;
			}
			for(double key : map.keySet()){
				max = Math.max(max, duplicate + map.get(key));
			}
			
		}
		return max;
	}
分享到:
评论

相关推荐

    leetcodemaxpointsonaline-leetcode:leetcode

    max points on a line leetcode ISCAS15 - leetcode - week1 唐波 任杰 王建飞 殷康 张一鸣 ISCAS15 - leetcode - week2 曾靖 刘重瑞 沉雯婷 刘旭斌 王建飞 ISCAS15 - leetcode - week3 殷康 张一鸣 赵伟 任杰 唐波 ...

    python-leetcode题解之149-Max-Points-on-a-Line.py

    python python_leetcode题解之149_Max_Points_on_a_Line.py

    js-leetcode题解之149-max-points-on-a-line.js

    javascript js_leetcode题解之149-max-points-on-a-line.js

    LeetCode最全代码

    Up to date (2016-12-18), there are `447` Algorithms / `13` Database / `4` Shell / `4` Draft questions on [LeetCode Online Judge](https://leetcode.com/). The number of questions is increasing recently...

    dna匹配leetcode-leetcode:leetcode刷题

    dna匹配 leetcode leetcode刷题--C++ 哈希表 Longest Substring Without Repeating Characters ...Points on a Line 斜率 map, int&gt; Fraction to Recurring Decimal map long long 正负号 Repeated DNA S

    LeetCode:LeetCode解决方案

    LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...

    Selective_Leetcode_solutions

    2. 题目149 - "Max Points on a Line" 这道题目要求找到平面上最多共线的点。解决方法通常涉及线性代数,如计算两点之间的斜率,并通过哈希表记录斜率及其出现的次数。在Java中,可以使用HashMap来存储斜率和对应的...

    leetcodemaxpointsonaline-leetcode:https://oj.leetcode.com/的解决方案

    在LeetCode平台上,题目"Max Points on a Line"是一道典型的几何与图论结合的问题,旨在测试编程者对数据结构和算法的理解。本题要求找到二维平面上最多共线的点的数量。这个问题的关键在于理解如何有效地计算每一对...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    2. **Max points on a line** (平面上最多的共线点): 此题考察的是线性代数和几何知识,以及如何在二维平面上找到共线点。在Java中,可以使用数据结构如HashMap来存储斜率和点的数量,从而有效地计算最大共线点数。 ...

Global site tag (gtag.js) - Google Analytics