LeetCode:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
程序员文章站
2022-04-01 19:22:29
...
题目描述
对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
解题思路:循环遍历每个点,先统计其他点与当前点的重合个数dup以及与当前点在同一条垂直线上vlt的个数(斜率不存在的情况),再统计其他点与当前点在同一条直线的个数(斜率存在的情况),可利用HashMap统计这个点相对于其他点的不同斜率的个数,最后比较得到最多的在同一条直线上的点个数。
Java代码实现:
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
import java.util.*;
public class Solution {
public int maxPoints(Point[] points) {
int len = points.length;
if(len < 2)
return len;
int max_points = 0;
for(int i = 0; i < len; i++){
int dup = 0, vlt = 0; //重合个数,垂直个数
Point a = points[i];
Map<Float,Integer> map = new HashMap<>(); //key为斜率
for(int j = 0; j < len; j++){
if(i == j) continue;
else{
Point b = points[j];
if(a.x == b.x){
if(a.y == b.y) dup++;
else vlt++;
}
else{
float k = (float)(b.y - a.y)/(b.x - a.x);
if(map.get(k) == null) map.put(k, 1);
else map.put(k, 1 + map.get(k));
}
}
}
int max = vlt;
for(float k :map.keySet()){
max = Math.max(max, map.get(k));
}
max_points = Math.max(max_points, max + dup); //加上重复点的个数
}
return max_points + 1;
}
}
推荐阅读
-
leetcode 给定二维平面上的n个点,找到位于同一直线上的最大点数
-
编程题—给定位于二维平面上的n个点,求出位于同一条直线上的最大点数
-
给定二维平面上的n个点,找到位于同一直线上的最大点数
-
LeetCode:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
[leetcode]给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
Leetcode打卡2:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
给定二维平面上的n个点,找出位于同一直线上的点的最大数目
-
对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上java实现
-
枚举:对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上
-
对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上