max-points-on-a-line(最多有多少个点位于同一条直线上)
程序员文章站
2022-04-01 17:56:06
...
问题一:如何确定点在同一个直线上? 可以选定一个点,然后根据其他的点到这个点的斜率来判断在同一直线上的点的数目。
问题二:如果点和选定的点是垂直的关系怎么办??就是不能直接求斜率了,因为分母为0, 那就直接用一个变量记录就好啦。
问题三:如果点和选定的点是重复的怎么办??也是把重复的点记录下来,到时候返回最终结果的时候加上重复的点的个数就好了。
思路:遍历每个点,即定一个点, 用map容器记录该点与其他点的斜率,并统计该斜率的次数(相当于记录有多少个点位于同一条直线上)
对于和选定的点垂直的点(即斜率不存在) 和 重合的点要分开记录。
class Solution {
public:
int maxPoints(vector<Point> &points) {
int n = points.size();
if(n <= 0)
return 0;
int res = 0;
for(int i = 0; i < n; i++){
map<double, int>m;//键记录斜率,值记录在同一条直线的点的个数
int vertical = 0;//因和points[i]垂直而在同一条直线的点的个数
int dup = 0;//和points[i]重复的点的个数
int curMax = 1;//当前最大的在同一条直线的点的个数
for(int j = 0; j < n; j++){//选定一个点
if(j != i){
double x = points[i].x - points[j].x;
double y = points[i].y - points[j].y;
if(x == 0 && y == 0){//点重合
dup++;
}
else if(x == 0){//点垂直定点
if(vertical == 0)
vertical = 2;
else
vertical++;
}
else{
double k = y / x;
if(m[k] == 0)
m[k] = 2;
else
m[k]++;//斜率为K的点的个数增加,即同一条直线的点个数相加
}
}
}
//求最大的在同一条直线的上的点的个数(不包括重复的点)
curMax = max(curMax, vertical);
for(map<double, int>::iterator it = m.begin(); it != m.end(); it++){
if(it->second > curMax)
curMax = it->second;
}
//记得加上重复的点才是最终的在同一条直线上的点的数目
res = max(res, curMax + dup) ;
}
return res;
}
};
JAVA版本:
在这里插入代码片
package Leetcode;
import java.util.HashMap;
import java.util.Iterator;
class Point {
int x;
int y;
Point() { x = 0; y = 0; }
Point(int a, int b) { x = a; y = b; }
}
public class Solution {
public static int maxPoints(Point[] points) {
if(points == null)
return 0;
int n = points.length;
if(n <= 0)
return 0;
int res = 0;
for(int i = 0; i < n; i++) {
HashMap<Double, Integer> m = new HashMap<>();
int curMax = 1;
int dup = 0;
int ver = 0;
for(int j = 0; j < n; j++) {
if(j != i) {
double x = points[i].x - points[j].x;
double y = points[i].y - points[j].y;
if(x == 0 && y == 0)
dup++;
else if(x == 0) {
if(ver == 0)
ver = 2;
else
ver++;
}
else {
double k = y / x;
//m.containKey(key)判断key是否存在map容器
//利用m.put加入容器
//m.get来获取容器的value
if(m.containsKey(k) == false) {
m.put(k, 2);
}
else {
m.put(k, m.get(k) + 1);
}
}
}
}
curMax = Math.max(curMax, ver);
//利用迭代器访问map容器
Iterator<Double> iterator = m.keySet().iterator();
while(iterator.hasNext()) {
double key = iterator.next();
int tmp = m.get(key);
if(tmp > curMax)
curMax = tmp;
}
res = Math.max(res, curMax + dup);
}
return res;
}
public static void main(String args[]) {
Point a = new Point(2, 3);
Point b = new Point(3, 3);
Point c = new Point(-5, 3);
Point[] points = new Point[3];
points[0] = a;
points[1] = b;
points[2] = c;
int res = maxPoints(points);
System.out.println(res);
}
}
上一篇: 计算几何基础_多边形面积
下一篇: 1127. 多边形面积(计算几何)