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; }
相关推荐
max points on a line leetcode ISCAS15 - leetcode - week1 唐波 任杰 王建飞 殷康 张一鸣 ISCAS15 - leetcode - week2 曾靖 刘重瑞 沉雯婷 刘旭斌 王建飞 ISCAS15 - leetcode - week3 殷康 张一鸣 赵伟 任杰 唐波 ...
python python_leetcode题解之149_Max_Points_on_a_Line.py
javascript js_leetcode题解之149-max-points-on-a-line.js
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刷题--C++ 哈希表 Longest Substring Without Repeating Characters ...Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
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-...
2. 题目149 - "Max Points on a Line" 这道题目要求找到平面上最多共线的点。解决方法通常涉及线性代数,如计算两点之间的斜率,并通过哈希表记录斜率及其出现的次数。在Java中,可以使用HashMap来存储斜率和对应的...
在LeetCode平台上,题目"Max Points on a Line"是一道典型的几何与图论结合的问题,旨在测试编程者对数据结构和算法的理解。本题要求找到二维平面上最多共线的点的数量。这个问题的关键在于理解如何有效地计算每一对...
2. **Max points on a line** (平面上最多的共线点): 此题考察的是线性代数和几何知识,以及如何在二维平面上找到共线点。在Java中,可以使用数据结构如HashMap来存储斜率和点的数量,从而有效地计算最大共线点数。 ...