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.
一个平面中有很多点,找出能在同一条直线上的最多的点
思路:遍历所有的点,在每次遍历中再依次遍历其他与该点没有计算过斜率的点,计算斜率,并统计数量。
/** * Definition for a point. * class Point { * int x; * int y; * Point() { x = 0; y = 0; } * Point(int a, int b) { x = a; y = b; } * } */ public class Solution { public int maxPoints(Point[] points) { if(points.length==0) return 0; int max = 1; //第一个值存放斜率,第二个存放数量 Map<Double,Integer> map = new HashMap<Double,Integer>(); for(int i=0;i<points.length-1;i++) { int x=1; int duplicates = 0; boolean flag = false; int tempmax = 1; map.clear(); for(int j=i+1;j<points.length;j++) { //计算重复点 if(points[j].x==points[i].x&&points[i].y==points[j].y) { duplicates++; continue; } //判断是否两点共x轴 if(points[j].x-points[i].x!=0) { double k = (double)(points[j].y-points[i].y)/(points[j].x-points[i].x); if(k==-0.0) k=0.0; if(map.get(k)==null) { map.put(k, 2); if(tempmax<2) tempmax=2; } else { int t = (Integer)map.get(k); t=t+1; map.put(k,t); if(t>tempmax) tempmax=t; } }else { x++; } } if(tempmax+duplicates>max) max = duplicates+tempmax; if(x>max) max=x; } 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来存储斜率和点的数量,从而有效地计算最大共线点数。 ...