多少个点位于同一直线-Java
程序员文章站
2022-04-01 17:29:14
...
对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
思路
穷举每个点,计算a与b的斜率。需要注意有一些特殊点,比如重复的点,和x相等但y不相等的点(算斜率时会除零)。重复的点,最终计算max时需要计入。垂直的点,比较一下该点的个数与max的大小即可。
import java.util.*;
/*
* public class Point {
* int x;
* int y;
* }
*/
public class Solution {
/**
*
* @param points Point类一维数组
* @return int整型
*/
public int maxPoints (Point[] points) {
int res = 0;
// write code here
if(points == null || points.length == 0){
return 0;
}
if(points.length < 3){
return points.length;
}
for(int i = 0; i < points.length; i++){
int duplicatePoint = 1; //重复的点
int vartialPoint = 0; //垂直的点,因为垂直的算不出斜率
Point a = points[i];
HashMap<Float, Integer> map = new HashMap<Float, Integer>();
for(int j = 0; j < points.length; j++){
if(i == j){
continue;
}
Point b = points[j];
if(b.x == a.x){ //先算特殊点
if(b.y == a.y){
duplicatePoint++;
}else{
vartialPoint++;
}
}else{ //非特殊点就正常算斜率
float k = (float)(a.y - b.y) / (a.x - b.x); //这里一定要强转一下,否则20组样例只能过13组
if(map.containsKey(k)){
map.put(k, map.get(k) + 1);
}else{
map.put(k, 1);
}
}
}
int max = vartialPoint;
for(float k : map.keySet()){
max = Math.max(map.get(k), max);
}
res = Math.max(res, max + duplicatePoint);
}
return res;
}
}
推荐阅读
-
C4D贝塞尔曲线的两点怎么放到同一水平直线上?
-
leetcode 给定二维平面上的n个点,找到位于同一直线上的最大点数
-
编程题—给定位于二维平面上的n个点,求出位于同一条直线上的最大点数
-
给定二维平面上的n个点,找到位于同一直线上的最大点数
-
每天一道LeetCode-----平面上n个点,计算最多有多少个点在一条直线上
-
LeetCode:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
给定2D平面上的n个点,找到位于同一直线上的最大点数
-
求最多能有多少个点位于同一直线上
-
[leetcode]给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
Leetcode打卡2:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上