本文共 677 字,大约阅读时间需要 2 分钟。
最多有多少个点在一条直线上
给出二维平面上的n个点,求最多有多少点在同一条直线上。
样例
给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。一条直线上的点最多有3个。
问题分析:
可以根据A点跟其他点所构成线段的斜率判断与A点共线的点的个数.遍历所有点,取出最大值即可, 1.考虑重复点的情况. 2.考虑斜率为无穷大的情况.import java.util.HashMap;//定义坐标点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==null||points.length==0){ return 0; }//建立Hash表 HashMapmap= new HashMap (); int max=1; for(int i=0;i max){ max=temp+dup; } } } return max; }}
转载地址:http://svwxi.baihongyu.com/