1.问题描述
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
2.翻译
对于在一个平面上的N个点，找出在同一条直线的最多的点的数目
3.思路分析
我们知道任意的两个点可以构成一条直线，对于一条在直线的上的点，他们必然具有相同的斜率，这个我初中都知道了。因为找出最多的点的方法也就比较简单了，我们只要依次遍历这些点，并且记录相同的斜率的点的数目，这样数目最大的那个斜率对应的值就是我们所需要的那个最大值了，因为我们需要一个HashMap,key用来存放斜率，value用来记录点的数目，最后我们只需要拿出value最大的那个 值就可以了。因为HashMap的底层采用hash实现，所以在查找比对的过程中效率还是比较高的。
4.实现代码
Solution.java()（实现过程借鉴了别人的实现，但是解题的思路是自己的）
package maxPoints;
import java.util.HashMap;
public class Solution {
public int maxPoints(Point[] points) {
if(points.length <= 2) {//如果点的数目小于等于2，那么一直线上的点就是数组的长度了
return points.length;
}
double k = 0.0;//斜率
int maxPointNum = 0;
int tempMaxPointNum = 0;
int samePointNum = 0;//坐标完全相同点的个数
int parallelPointNum = 0; //与x轴平行
HashMap<Double,Integer> slopeMap = new HashMap<Double,Integer>();
for(int i=0;i<points.length-1;i++) {
samePointNum = 1; //代表起始点，会被累加上
parallelPointNum = 0;
tempMaxPointNum = 0;
slopeMap.clear();
for(int j=i+1;j<points.length;j++) {
if((points[i].x == points[j].x)&&((points[i].y == points[j].y))) {//坐标完全相同
samePointNum++;
continue;
}
if(points[i].x == points[j].x) { //与y轴平行
parallelPointNum++;
} else {
if(points[i].y == points[j].y) {
k = 0;
} else {
k = ((double)(points[i].y - points[j].y))/(points[i].x - points[j].x);
}
if(slopeMap.get(k) == null) {//斜率不存在
slopeMap.put(k, new Integer(1));
if(1>tempMaxPointNum) {
tempMaxPointNum = 1;
}
}else {//斜率已存在
int number = slopeMap.get(k);
number++;
slopeMap.put(k, new Integer(number));
if(number>tempMaxPointNum) {
tempMaxPointNum = number;
}
}
}
}
if(parallelPointNum > 1) {
if(parallelPointNum>tempMaxPointNum) {
tempMaxPointNum = parallelPointNum;
}
}
tempMaxPointNum += samePointNum;//加上起始点和具有相同坐标的点
if(tempMaxPointNum>maxPointNum) {
maxPointNum = tempMaxPointNum;
}
}
return maxPointNum;
}
}
SoultionTest.java
package maxPoints;
import java.util.Random;
public class SolutionTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Point []pointArr = new Point[100];
for(int index = 0;index < 100;index++){
Point point = new Point(index,new Random(index).nextInt());
pointArr[index] = point;
System.out.println("Point("+point.x+","+point.y+")");
}
System.out.println(new Solution().maxPoints(pointArr));
}
}
结果：
Point(0,-1155484576)
Point(1,-1155869325)
Point(2,-1154715079)
Point(3,-1155099828)
Point(4,-1157023572)
Point(5,-1157408321)
Point(6,-1156254074)
Point(7,-1156638823)
Point(8,-1158562568)
Point(9,-1158947317)
Point(10,-1157793070)
Point(11,-1158177819)
Point(12,-1160101563)
Point(13,-1160486312)
Point(14,-1159332065)
Point(15,-1159716814)
Point(16,-1149328594)
Point(17,-1149713343)
Point(18,-1148559096)
Point(19,-1148943845)
Point(20,-1150867590)
Point(21,-1151252339)
Point(22,-1150098092)
Point(23,-1150482841)
Point(24,-1152406585)
Point(25,-1152791334)
Point(26,-1151637087)
Point(27,-1152021836)
Point(28,-1153945581)
Point(29,-1154330330)
Point(30,-1153176083)
Point(31,-1153560832)
Point(32,-1167796541)
Point(33,-1168181290)
Point(34,-1167027043)
Point(35,-1167411792)
Point(36,-1169335537)
Point(37,-1169720286)
Point(38,-1168566039)
Point(39,-1168950788)
Point(40,-1170874532)
Point(41,-1171259281)
Point(42,-1170105035)
Point(43,-1170489784)
Point(44,-1172413528)
Point(45,-1172798277)
Point(46,-1171644030)
Point(47,-1172028779)
Point(48,-1161640559)
Point(49,-1162025308)
Point(50,-1160871061)
Point(51,-1161255810)
Point(52,-1163179554)
Point(53,-1163564303)
Point(54,-1162410057)
Point(55,-1162794806)
Point(56,-1164718550)
Point(57,-1165103299)
Point(58,-1163949052)
Point(59,-1164333801)
Point(60,-1166257546)
Point(61,-1166642295)
Point(62,-1165488048)
Point(63,-1165872797)
Point(64,-1180108506)
Point(65,-1180493255)
Point(66,-1179339008)
Point(67,-1179723757)
Point(68,-1181647502)
Point(69,-1182032251)
Point(70,-1180878004)
Point(71,-1181262753)
Point(72,-1183186497)
Point(73,-1183571246)
Point(74,-1182416999)
Point(75,-1182801748)
Point(76,-1184725493)
Point(77,-1185110242)
Point(78,-1183955995)
Point(79,-1184340744)
Point(80,-1173952524)
Point(81,-1174337273)
Point(82,-1173183026)
Point(83,-1173567775)
Point(84,-1175491519)
Point(85,-1175876268)
Point(86,-1174722021)
Point(87,-1175106770)
Point(88,-1177030515)
Point(89,-1177415264)
Point(90,-1176261017)
Point(91,-1176645766)
Point(92,-1178569510)
Point(93,-1178954259)
Point(94,-1177800013)
Point(95,-1178184762)
Point(96,-1192420471)
Point(97,-1192805220)
Point(98,-1191650973)
Point(99,-1192035722)
6
从结果输出了可以看出在通一条直线上最多的点是6个。
5.这个题的解决方法很暴力，可是还有很多细节需要注意，比如斜率为0 的情况，斜率不存在的情况，还有点重合的情况，等等。