对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上
[编程题]多少个点位于同一直线
题目描述
解题思路
点共线，那么最容易想到的思路就是确定斜率，斜率相同不就共线了。但是还有两点特殊情况需要考虑，二是当两个点重合时，无法确定一条直线，但这也是共线的情况，需要特殊处理。二是斜率不存在的情况，由于两个点(x1, y1)和(x2, y2)的斜率k表示为(y2 - y1) / (x2 - x1)，那么当x1 = x2时斜率不存在，这种共线情况需要特殊处理。这里我对重合的情况，斜率不存在的情况以及斜率为0的情况进行了讨论，因为这比较好处理，所以处理一下斜率为0的没什么问题。最后就是通用情况，代码如下：
class Solution {
public int maxPoints(Point[] points) {
if(points == null){
return 0;
}
if(points.length <= 2){
return points.length;
}
Map map = new HashMap();
int result = 0;
for(int i=0;i<points.length;i++){
map.clear();
int overlap = 0;
int vertical = 0;
int horizon = 0;
int max = 0;
double rate = 0.0;
for(int j=i+1;j<points.length;j++){
double gapx = new Double(points[i].x) - new Double(points[j].x);
double gapy = new Double(points[i].y) - new Double(points[j].y);
if(gapx == 0 && gapy == 0){
overlap++;
continue;
}else if(gapx == 0){
vertical++;
max = Math.max(max,vertical);
}else if(gapy == 0){
horizon++;
max = Math.max(max,horizon);
}else{
rate = gapy/gapx;
if(map.containsKey(rate)){
map.put(rate,map.get(rate)+1);
}else{
map.put(rate,1);
}
max = Math.max(max,map.get(rate));
}
}
result=Math.max(result, max+overlap+1);
}
return result;
}
}虽然可以在牛客上通过，但是这个思路在leetcode上已经不行了，它给的例子是：
Input [[0,0],[94911151,94911150],[94911152,94911151]]
Output 3
Expected 2我们注意到，由于精度丢失问题，我们算出来的斜率竟然是一样的了，所以这个程序错误地认为这三个点都共线了。因此错误。那怎么办呢？
代码提交
由于通过斜率来判断共线需要用到除法，而用double表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，我们应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，我们把除数和被除数都保存下来，不做除法，但是我们要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现我们的目标。
class Solution {
public int maxPoints(Point[] points) {
if(points == null){
return 0;
}
if(points.length <= 2){
return points.length;
}
//key为每个数组除以最大公约数后的结果，比如[8,4],[4,2],[2,1]最后都变成[2,1]存储
Map,Integer> map = new HashMap();
int result = 0;
for(int i=0;i<points.length;i++){
//每次循环完毕要清空map，否则会把上次统计结果带到下一次循环来
map.clear();
//重复个数，自己算重复元素，所以初始元素为1
int dup = 1;
int max = 0;
for(int j=i+1;j<points.length;j++){
//计算出两者间隔
int x = points[i].x - points[j].x;
int y = points[i].y - points[j].y;
//重合的话就将dup加一
if(x == 0 && y == 0){
dup++;
continue;
}
//计算最大公约数
int d = gcd(x, y);
Map tmpMap = new HashMap();
tmpMap.put(x/d,y/d);
//次数
map.put(tmpMap, map.getOrDefault(tmpMap, 0) + 1);
//每次都将最大的放到max中，避免最后还要遍历判断map中最大次数
max = Math.max(max,map.get(tmpMap));
}
//最后的结果就是map+dup
result = Math.max(result,max+dup);
}
return result;
}
public int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
}
编辑于 2019-03-21 12:37:01
回复(9)
需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。
a和b如果不重合，就可以确定一条直线。
对于每个点a，构建 斜率->点数 的map。
(1)b与a重合，以a起始的所有直线点数+1 (用dup统一相加)
(2)b与a不重合，a与b确定的直线点数+1
/** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(int a, int b) : x(a), y(b) {} * }; */ class Solution { public: int maxPoints(vector<Point> &points) { int size = points.size(); if(size == 0) return 0; else if(size == 1) return 1; int ret = 0; for(int i = 0;i<size;i++){ int curmax = 1; map<double,int>mp; int vcnt = 0; //垂直点 int dup = 0; //重复点 for(int j = 0;j<size;j++){ if(j!=i){ double x1 = points[i].x - points[j].x; double y1 = points[i].y - points[j].y; if(x1 == 0 && y1 == 0){ //重复 dup++; }else if(x1 == 0){ //垂直 if(vcnt == 0) vcnt = 2; else vcnt++; curmax = max(vcnt,curmax); }else{ double k = y1/x1; //斜率 if(mp[k] == 0) mp[k] = 2; else mp[k]++; curmax = max(mp[k],curmax); } } } ret = max(ret,curmax+dup); } return ret; } };
发表于 2016-04-05 16:15:34
回复(31)
/**
* 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 n = points.length;
if(n < 2) return n;
int ret = 0;
for(int i = 0; i < n; i++) {
// 分别统计与点i重合以及垂直的点的个数
int dup = 1, vtl = 0;
Map<Float, Integer> map = new HashMap<>();
Point a = points[i];
for(int j = 0; j < n; j++) {
if(i == j) continue;
Point b = points[j];
if(a.x == b.x) {
if(a.y == b.y) dup++;
else vtl++;
} else {
float k = (float)(a.y - b.y) / (a.x - b.x);
if(map.get(k) == null) map.put(k, 1);
else map.put(k, map.get(k) + 1);
}
}
int max = vtl;
for(float k: map.keySet()) {
max = Math.max(max, map.get(k));
}
ret = Math.max(ret, max + dup);
}
return ret;
}
}
编辑于 2016-10-05 00:50:10
回复(12)
//本方法在高票答案的基础上做了以下优化：
//1、map的键值修改为：对斜率保留6位小数的string，以避免浮点数直接比较
//2、内存循环从i+1开始，避免不必要的循环
//3、对于高票答案中讨论的vCn，dCn 初值设为1的“优化方案”进行否定，
//因为初值为1可能导致一些边界异常，需要在结尾处处理异常，反而增加了工作量
class Solution {
public:
int maxPoints(vector<Point> &points) {
if(points.size() == 0)
return 0;
else if(points.size() == 1)
return 1;
int res = 1;
for(size_t i = 0; i < points.size(); ++i){
map<string, int>info;
int vCn = 0/*垂直点 */, dCn = 0/*重复点 */, curMax = 1/*当前最大连接点数 */;
for(size_t j = i+1; j < points.size(); ++j){
double x_dis = points[i].x - points[j].x;
double y_dis = points[i].y - points[j].y;
if(compare(points[i].x , points[j].x) && compare(points[i].y , points[j].y) ){
++dCn;
}
else if( compare(x_dis, 0.0) ) {
if(vCn == 0)
vCn = 2;
else
++vCn;
curMax = curMax > vCn ? curMax : vCn;
}
else{
double k = y_dis/x_dis;
string sk = transform(k);
if(info[sk] == 0)
info[sk] = 2;
else
++info[sk];
curMax = curMax > info[sk] ? curMax : info[sk];
}
}
res = res > curMax + dCn ? res : curMax + dCn;
}
return res;
}
string transform(double d){
ostringstream os;
os << ( (int)(d * 1000000 + 0.5) ) / 1000000.0;
return os.str();;
}
bool compare(double a, double b){
if( fabs(a - b) < 1e-6)
return true;
else
return false;
}
};
发表于 2017-07-12 23:29:51
回复(3)
import java.util.*;
public class Solution {
public int maxPoints(Point[] points) {
if(points.length < 2) return points.length;
int max = 0;
for (int i = 0; i < points.length; i ++) {
Map<Float, Integer> map = new HashMap<>();
int chonghe = 0, chuizhi = 0;
Point a = points[i];
for (int j = 0; j < points.length; j ++) {
if(i == j) continue;
Point b = points[j];
if(a.x == b.x) {
if(a.y == b.y) chonghe ++;
else chuizhi ++;
} else {
float k = (float)(a.y - b.y) / (a.x - b.x);
map.put(k, map.get(k) == null ? 1 : map.get(k) + 1);
}
}
int temp_max = chuizhi;
for (Float k:map.keySet()) {
temp_max = temp_max > map.get(k) ? temp_max : map.get(k);
}
max = max > temp_max + chonghe + 1 ? max : temp_max + chonghe + 1;
}
return max;
}
}
发表于 2017-03-16 22:55:15
回复(5)
用浮点数储存斜率有可能会有浮点数误差。
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point> &points) {
sort(points.begin(), points.end(), [](Point a, Point b){return a.x < b.x;});
long long ans = 0;
for (int i = 0; i < points.size(); i++)
{
map<pair<int, int>, long long> k;
long long multi = 0, vertical = 0, maxk = 0;
for (int j = i + 1; j < points.size(); j++)
{
if (points[i].x == points[j].x && points[i].y == points[j].y)
{
multi++;
}
else if (points[i].x == points[j].x)
{
maxk = max(maxk, ++vertical);
}
else
{
int x = points[j].x - points[i].x;
int y = points[j].y - points[i].y;
int g = __gcd(x, y);
x /= g, y /= g;
maxk = max(maxk, ++k[make_pair(x, y)]);
}
}
ans = max(ans, maxk + multi + 1);
}
return ans;
}
};
发表于 2017-06-25 16:39:43
回复(9)
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
classSolution {
public:
intmaxPoints(vector<Point> &points) {
if(points.size() == 0) return0;
if(points.size() == 1) return1;
intmaxPoints = 2;
intn = points.size();
for(inti = 0; i < n - 1; i++) {
for(intj = i + 1; j < n; j++) {
intnumPoints = 2;
if(points[i].x == points[j].x) {
for(intk = 0; k < n; k++) {
if(points[k].x == points[i].x && k !=
i && k != j) {
numPoints++;
}
}
}
else{
for(intk = 0; k < n; k++) {
intijDx = points[j].x - points[i].x, ijDy =
points[j].y - points[i].y,
ikDx = points[k].x - points[i].x, ikDy =
points[k].y - points[i].y;
if(k != i && k != j && ijDx *
ikDy == ijDy * ikDx)
numPoints++;
}
}
if(numPoints > maxPoints) maxPoints = numPoints;
}
}
returnmaxPoints;
}
};
发表于 2017-06-05 21:30:40
回复(1)
//参考了排名最高的回答，但是不可以采用double形式来表达，因为会产生精度误差，我们可以
//使用分数的形式来表示斜率，使用分子分母同除以最大公倍数即可得到最简分数；
class Solution {
public:
int maxPoints(vector<Point> &points) {
int size = points.size();
if(size<=2) return size;
int ret = 0;
for(int i = 0;i<size;i++)
{
int curmax = 0;
map<string,int>mp;
int vcnt = 0; //垂直点
int dup = 0; //重复点
for(int j = 0;j<size;j++)
{
int x1 = points[i].x - points[j].x;
int y1 = points[i].y - points[j].y;
if(x1==0 && y1==0)
dup++;
else if(y1==0)
{
++vcnt;
curmax = max(curmax,vcnt);
}
else
{
string key = gcb(y1,x1);
++mp[key];
curmax = max(curmax,mp[key]);
}
}
ret = max(ret,curmax+dup);
}
return ret;
}
string gcb(int y1,int x1) //使用分子分母表示最简分数
{
if(x1==0)
return "shuipin";
int a = y1;
int b = x1;
int temp;
while(a%b)
{
temp = a%b;
a = b;
b = temp;
}
return to_string(y1/b) + "/" + to_string(x1/b);
}
};
发表于 2018-08-05 14:38:29
回复(2)
穷举...要考虑到特殊情况，斜率不存在、点重合、HashMap里-0.0和0.0是不同的key...
public int maxPoints(Point[] points) {
Double k;
int x, y, max = 0;
for(int i = 0; i < points.length; i++) {
HashMap<Double, Integer> map = new HashMap<Double, Integer>();
int curMax = 1, repNum = 0;
x = points[i].x; y = points[i].y;
for(int j = i + 1; j < points.length; j++) {
int num = 1;
if(x == points[j].x && y == points[j].y)
repNum += 1;
else {
if(x != points[j].x)
if(y == points[j].y) k=0.0;
else k = 1.0*(y - points[j].y) / (x - points[j].x);
else
k = Double.MAX_VALUE;
if(map.get(k) != null)
num = map.get(k) + 1;
else
num = 2;
map.put(k, num);
}
if(curMax < num) curMax = num;
}
curMax += repNum;
if(max < curMax) max = curMax;
}
return max;
}
编辑于 2016-10-08 16:38:18
回复(0)
class Solution {
public:
bool CalculateLine(const Point& p1,
const Point& p2,
vector<double>* line_para_ptr) {
vector<double>& line_para = *line_para_ptr;
if (p1.x - p2.x == 0)
return false;
double k = (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
double b = p2.y - p2.x * k;
line_para.push_back(k);
line_para.push_back(b);
return true;
}
bool JudgePointAtLine(const Point& p,
const vector<double>& line_para) {
return abs(p.y - line_para[0] * p.x - line_para[1]) < 1e-8;
}
int maxPoints(vector<Point>& points) {
int nsize = points.size();
if (nsize == 0)
return 0;
else if (nsize == 1)
return 1;
else if (nsize == 2)
return 2;
int maxpoints = 0;
vector<set<int>> common_line_points_index;
common_line_points_index.resize(nsize);
for (int i = 0; i < nsize; i++) {
for (int j = i + 1; j < nsize; j++) {
if (common_line_points_index[j].count(i))
continue;
bool have_gradient;
vector<double> line_par;
int numpoints = 2;
have_gradient = CalculateLine(points[i], points[j], &line_par);
common_line_points_index[i].insert(j);
common_line_points_index[j].insert(i);
for (int k = 0; k < nsize; k++) {
if (k == i || k == j)
continue;
if (!have_gradient) {
if (points[k].x == points[j].x)
numpoints++;
} else {
if (JudgePointAtLine(points[k],line_par))
numpoints++;
}
}
maxpoints = max(maxpoints, numpoints);
}
}
return maxpoints;
}
};
发表于 2019-09-14 20:25:35
回复(0)
class Solution {
public:
int maxPoints(vector<Point> &points) {
int n = points.size();
if(n <= 1)
return n;
int count = 0;
for(int i=0;i<n;i++)
{
map<pair<int,int>,int> M; int d = 1; for(int j=i+1;j<n;j++) { if(points[i].x==points[j].x && points[i].y==points[j].y) { d++; continue; } int dx = points[j].x - points[i].x; int dy = points[j].y - points[i].y; int g = gcd(dx, dy); M[{dx/g, dy/g}]++; } count = max(count, d); for(auto it=M.begin();it!=M.end();it++) count = max(count, it->second + d); } return count;
}
int gcd(int a,int b)
{
return (b==0)?a:gcd(b,a%b); }
};
发表于 2017-10-07 01:24:36
回复(0)
/**
* 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.HashMap;
import java.util.Map;
public class Solution {
public int maxPoints(Point[] points) {
if (points == null)
return 0;
if (points.length <= 2)
return points.length;
Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
int res=0;
int max=0;
for (int i = 0; i < points.length - 1; i++) {
map.clear();
int overLap = 0;
max=0;
for (int j = i + 1; j < points.length; j++) {
int x = points[j].x - points[i].x;
int y = points[j].y - points[i].y;
if (x == 0 && y == 0){
overLap++;
continue;
}
// 计算最大公约数：欧几里得算法
// 因为用分数代替斜率，所以必须保证分子分母最简
int gcd = generateGCD(x, y);
if (gcd != 0) {
x = x / gcd;
y = y / gcd;
}
if (map.containsKey(x)) {
if (map.get(x).containsKey(y))
map.get(x).put(y, map.get(x).get(y) + 1);
else
map.get(x).put(y, 1);
} else {
Map<Integer,Integer> temp=new HashMap<Integer,Integer>();
temp.put(y, 1);
map.put(x, temp);
}
max=Math.max(max,map.get(x).get(y));
}
res=Math.max(res, max+overLap+1);
}
return res;
}
private int generateGCD(int x, int y) {
if(y==0)
return x;
return generateGCD(y,x%y);
}
}
发表于 2017-08-01 12:35:05
回复(0)
class Solution {
public:
int maxPoints(vector<Point>& points)
{
int len = points.size();
if(len< 2)
return len;
int res = 0;
for(int i=0;i<len;i++)
{
map<pair<int,int>,int> slopeMap;
int duplicates = 1; // 自身重叠初始化为1
for(int j=i+1;j<len;j++)
{
// 重合
if(points[i].x == points[j].x && points[i].y == points[j].y)
{
duplicates++;
continue;
}
// 斜率不适用float作为键，精度损失，使用除以最小公约数后的pair作为键
int dix = points[j].x - points[i].x;
int diy = points[j].y - points[i].y;
int maxD = gcd(dix,diy);
slopeMap[{dix/maxD,diy/maxD}] ++;
}
res = max(res,duplicates);
for(auto it=slopeMap.begin();it!=slopeMap.end();it++)
res = max(res,it->second + duplicates);
}
return res;
}
int gcd(int a, int b)
{
return (b == 0) ? a : gcd(b, a % b);
}
};
发表于 2017-07-20 09:37:30
回复(1)
/*
*分为n、n-1、n-2……3等组（每组分别包含n个点、n-1个点……），找到每组中包含第一个点的点数最多的直线（每个点与第一个点有一个斜率，通过斜率是否相等判断是否在同一条直线），则每组结果的最大值即为所求；
*原理：所求直线所包含的点，一定有一个最靠前的i点，使得直线上所有点为i~1的子集，所求值即为i组的结果
*注意事项：1、存在与第一个点相同的点；2、使用浮点数不一定能准确的表示斜率，在此使用由String表示的分数来表示斜率
*/
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
class Solution {
public int maxPoints(Point[] points) {
int result=0;
if(points.length<3) return points.length;
for(int i=0;i<points.length-1;i++){
HashMap map=new HashMap();
int maxNum=0,sameAsI=0;
for(int j=i+1;j<points.length;j++){
String key=xieLv(points[i],points[j]);
if(points[i].x==points[j].x&&points[i].y==points[j].y) {
sameAsI++;
continue;
}else {
map.put(key,map.containsKey(key) ? map.get(key)+1:1);
}
maxNum= Math.max(maxNum,map.get(key));
}
result=Math.max(result,maxNum+sameAsI);
}
return result+1;
}
private String xieLv(Point a,Point b){
int x=a.x-b.x,y=a.y-b.y;
if(x==0) return fuHao(x,y)+"ANY"+"/"+0;
else if(y==0) return fuHao(x,y)+0+"/"+"ANY";
int gcb=gcb(Math.abs(y),Math.abs(x));
return fuHao(x,y)+Math.abs(y)/gcb+"/"+Math.abs(x)/gcb;
}
private String fuHao(int x,int y){
if(x>=0&&y>=0||x<=0&&y<=0){
return "+";
}else return "-";
}
private int gcb(int a,int b){
if(b==0) return a;
else return gcb(b,a%b);
}
}
发表于 2017-07-05 10:38:49
回复(1)
if(points.size() < 2)
return points.size();
int result = 0;
for(int i=0;i<points.size();++i)
{
//用来记录斜率和个数的Map
map, int> lines;
int localmax = 0, overlap = 0, vertical = 0;
for(int j=i+1;j<points.size();++j)
{
if(points[i].x == points[j].x&&points[i].y == points[j].y)
{
++overlap;
continue;
}else if(points[i].x == points[j].x)
{
++vertical;
localmax = max(localmax, vertical);
}else{
int x = points[j].x - points[i].x;
int y = points[j].y - points[i].y;
int gcd = GCD(x, y);
x /= gcd;
y /= gcd;
++lines[make_pair(x,y)];
localmax = max(localmax, lines[make_pair(x,y)]);
}
}
result = max(result, localmax+overlap+1);
}
return result;
}
private:
//求得最大公约数
int GCD(int a, int b)
{
if(b==0)
return a;
else
return GCD(b, a%b);
}
发表于 2017-02-06 15:25:38
回复(1)
最简单直接的思路:
1) 选择第一个点A1
2) 选择第二个点A2, 和第一个点构成一条直线,
3) 遍历剩下的n-2个点Ai, 判断Ai与A1构成的直线是否与A2与A1构成的直线保持一致,若是,则A1A2直线上的点数就+1;
4)每次求完A1A2直线上的最大点数, 和结果取最大值. 遍历结束就是结果
public class Solution {
public int maxPoints(Point[] points) {
if (null == points) {
return 0;
} else if (points.length < 3) {
return points.length;
}
int maxPoints = 2;
for (int i = 0; i < points.length; i++) {
int x1 = points[i].x;
int y1 = points[i].y;
for (int j = i + 1; j < points.length; j++) {
int x2 = points[j].x;
int y2 = points[j].y;
int max = 2;
for (int k = 0; k < points.length; k++) {
if (k == i || k == j) {
continue;
}
int x3 = points[k].x;
int y3 = points[k].y;
boolean flag;
if (x1 == x2) {
flag = x3 == x1;
} else if (y1 == y2) {
flag = y3 == y1;
} else {
flag = (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 -x1);
}
if (flag) {
max++;
}
}
maxPoints = Math.max(maxPoints, max);
}
}
return maxPoints;
}
}
发表于 2019-08-10 10:11:25
回复(4)
import java.util.*;
/*
只通过了70%，可能还有有一些细节没有考虑上吧。
*/
public class Solution {
/**
*
* @param points Point类一维数组
* @return int整型
*/
public int maxPoints (Point[] points) {
// write code here
int plen=points.length;
if (plen==0)
return 0;
if(plen==1)
return 1;
if(plen==2)
return 2;
//先处理重复点
ArrayList<Point>new_Points = new ArrayList<Point>();
int[]point_size=new int[plen];//记录每个点的重复次数
new_Points.add(points[0]);
point_size[0]=1;
boolean flag;int j;
for(int i=1;i<plen;i++){
flag=false;
for(j=0;j<new_Points.size()&&!flag;j++){
if(SamePoint(points[i],new_Points.get(j))){
point_size[j]++;
// System.out.println(points[i].x+" is same as "+new_Points.get(j).x+","+point_size[j]);
flag=true;
}
}//实在找不到才加入
if(!flag){
new_Points.add(points[i]);
point_size[j]=1;
}
}
return maxP(new_Points,point_size);
}
//去重之后计算在同一条直线上的点
static public int maxP(ArrayList<Point> points,int[]point_s){
int plen=points.size();
if(plen==1)
return point_s[0];
if(plen==2)
return point_s[0]+point_s[1];
int maxP=2,currentP;
for(int i=0;i<plen-2;i++){
Point p1=points.get(i);
for(int j=i+1;j<plen-1;j++){
Point p2=points.get(j);
currentP=point_s[i]+point_s[j];
for(int w=j+1;w<plen;w++){
Point p3=points.get(w);
if(isLine(p1,p2,p3)){
currentP+=point_s[w];
}
}
if(currentP>maxP)
maxP=currentP;
}
}
// System.out.println(maxP);
return maxP;
}
static public boolean isLine(Point p1,Point p2, Point p3){//判断p3在不在p1和P2的线上
boolean flag=false;
//处理k=0的情况
if(p1.x==p2.x){
if(p3.x==p1.x)
return true;
else return false;
}
float k=(p2.y-p1.y)/(p2.x-p1.x);
if(p1.x==p3.x)
return false;
if(k==((p3.y-p1.y)/(p3.x-p1.x)))
flag=true;
return flag;
}
static public boolean SamePoint(Point p1,Point p2){
boolean flag=false;
if(p1.x==p2.x&&p1.y==p2.y)
flag=true;
return flag;
}
}
/*
只通过了70%，可能还有有一些细节没有考虑上吧。
*/
public class Solution {
/**
*
* @param points Point类一维数组
* @return int整型
*/
public int maxPoints (Point[] points) {
// write code here
int plen=points.length;
if (plen==0)
return 0;
if(plen==1)
return 1;
if(plen==2)
return 2;
//先处理重复点
ArrayList<Point>new_Points = new ArrayList<Point>();
int[]point_size=new int[plen];//记录每个点的重复次数
new_Points.add(points[0]);
point_size[0]=1;
boolean flag;int j;
for(int i=1;i<plen;i++){
flag=false;
for(j=0;j<new_Points.size()&&!flag;j++){
if(SamePoint(points[i],new_Points.get(j))){
point_size[j]++;
// System.out.println(points[i].x+" is same as "+new_Points.get(j).x+","+point_size[j]);
flag=true;
}
}//实在找不到才加入
if(!flag){
new_Points.add(points[i]);
point_size[j]=1;
}
}
return maxP(new_Points,point_size);
}
//去重之后计算在同一条直线上的点
static public int maxP(ArrayList<Point> points,int[]point_s){
int plen=points.size();
if(plen==1)
return point_s[0];
if(plen==2)
return point_s[0]+point_s[1];
int maxP=2,currentP;
for(int i=0;i<plen-2;i++){
Point p1=points.get(i);
for(int j=i+1;j<plen-1;j++){
Point p2=points.get(j);
currentP=point_s[i]+point_s[j];
for(int w=j+1;w<plen;w++){
Point p3=points.get(w);
if(isLine(p1,p2,p3)){
currentP+=point_s[w];
}
}
if(currentP>maxP)
maxP=currentP;
}
}
// System.out.println(maxP);
return maxP;
}
static public boolean isLine(Point p1,Point p2, Point p3){//判断p3在不在p1和P2的线上
boolean flag=false;
//处理k=0的情况
if(p1.x==p2.x){
if(p3.x==p1.x)
return true;
else return false;
}
float k=(p2.y-p1.y)/(p2.x-p1.x);
if(p1.x==p3.x)
return false;
if(k==((p3.y-p1.y)/(p3.x-p1.x)))
flag=true;
return flag;
}
static public boolean SamePoint(Point p1,Point p2){
boolean flag=false;
if(p1.x==p2.x&&p1.y==p2.y)
flag=true;
return flag;
}
}
发表于 2020-10-15 09:23:17
回复(0)
借用楼上的思想；穷举出各类，在垂直和水平的除外，利用三点式的直线方程确定累计；
import java.util.*;
/*
* public class Point {
* int x;
* int y;
* }
*/
public class Solution {
/**
*
* @param points Point类一维数组
* @return int整型
最简单直接的思路:
1) 选择第一个点A1
2) 选择第二个点A2, 和第一个点构成一条直线,
3) 遍历剩下的n-2个点Ai, 判断Ai与A1构成的直线是否与A2与A1构成的直线保持一致,若是,则A1A2直线上的点数就+1;
4)每次求完A1A2直线上的最大点数, 和结果取最大值. 遍历结束就是结果
*/
public int maxPoints (Point[] points) {
// write code here
if(points==null||points.length==0) return 0;
if(points.length<3) return points.length;
int maxPoints = 2;
for(int i=0;i<points.length;i++){
int x1 = points[i].x;
int y1 = points[i].y;
for(int j = i+1;j<points.length;j++){
int x2 = points[j].x;
int y2 = points[j].y;
int max = 2;
for(int k =0;k<points.length;k++){
if(k==i || k==j) continue;
int x3 = points[k].x;
int y3 = points[k].y;
boolean flag;
if(x1==x2){
flag= x3==x1;
}else if(y1==y2){
flag = y3==y1;
}else{
flag = (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1);//三点式直线方程
}
if(flag) max++;
}
maxPoints=Math.max(maxPoints,max);
}
}
return maxPoints;
}
}
发表于 2020-08-18 23:51:11
回复(0)
/**
* struct Point {
* int x;
* int y;
* };
*/
class Solution {
public:
/**
*
* @param points Point类vector
* @return int整型
*/
int maxPoints(vector<Point>& points) {
// write code here
size_t ps = points.size();
if(ps <=2) return ps;
int ans = 0;
for(size_t i=0; i<ps; ++i){
int groupmax = 0, dup = 1, ver = 0;
map<double, int> kgroup;
for(size_t j=i+1; j<ps; ++j){
double dx = points[i].x-points[j].x;
double dy = points[i].y-points[j].y;
if(dx==0 && dy==0)
++dup;
else if(dx==0){
++ver;
}else{
++kgroup[dy/dx];
groupmax = max(groupmax, kgroup[dy/dx]);
}
}
ans = max(ans, max(groupmax, ver) + dup);
}
return ans;
}
};
发表于 2020-07-07 20:50:23
回复(0)
import java.util.*;
/*
* public class Point {
* int x;
* int y;
* }
*/
public class Solution {
/**
*
* @param points Point类一维数组
* @return int整型
两层for循环遍历每两个点，总共考虑三种情况：
（1）两点重合
（2）两点垂直（因为两点垂直无法计算斜率）
（3）两点平行或者倾斜（计算斜率）
*/
public int maxPoints (Point[] points) {
if(points.length <= 2){
return points.length;
}
int count = 0;
for(int i = 0; i < points.length; i++){
HashMap<Float, Integer> map = new HashMap<>();//存放斜率以及斜率出现的次数
Point a = points[i];
int chonghe = 0;
int chuizhi = 0;
for(int j = 0; j < points.length; j++){
Point b = points[j];
if(i == j) continue;
if(a.x == b.x){
if(a.y == b.y){
chonghe++;//xy坐标均相等即重合的情况
}else{
chuizhi++;//x坐标相等y不相等，即垂直的情况
}
}else{ //第三种情况
float rate = (float)(b.y - a.y)/(b.x - a.x);
map.put(rate, map.get(rate) == null ? 1: map.get(rate) + 1);
}
int maxTemp = chuizhi;
for(Integer value : map.values()){ //计算斜率相同的点最多有多少个
maxTemp = maxTemp > value ? maxTemp : value;//与垂直的情况进行对比
}
count = count > maxTemp+chonghe+1 ? count : maxTemp+chonghe+1;
}
}
return count;
}
}
发表于 2020-06-10 18:38:52
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-10-07 22:36:23
-
2022-09-16 17:04:17 -
2022-09-16 03:53:13 -
2022-09-12 20:46:55 -
2022-09-10 19:35:38
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
