水中的鱼: [LeetCode] Max Points on a Line, Solution
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
http://yucoding.blogspot.com/2013/12/leetcode-question-max-points-on-line.html
First of all, how to know the points are on the same line? The slope!
The slope of a line can be computed using any two points (x1,y1) (x2,y2) on the line:
slop = (y2-y1)/(x2-x1) , x2!=x1.
X. Map<Pair<X,Y>, Integer>
http://blueocean-penn.blogspot.com/2015/01/find-straight-line-with-maximum-points.html
This problem tests our knowledge about two concepts: 1) relative prime or calculate GCD; 2) how hash table works, if we override equals(), we must override hashCode(). Again two simple and fundamental knowledges can solve this seemingly complex problems.
The algorithm has those steps:
Given list of n points, saying points[k] where k = 0, 1, ..., n-1
max: the maximum number of points on a line
1. for each point points[i], loop through any other points in the list points[j], where j!=i
2. representing the slope of the line by calculating a pair of numbers, (points[j].y-points[i].y, points[j].x-points[i].x)
if(points[j].x-points[i].x==0) which is a vertical line, then form a pair of numbers (1, 0)
else then divided by the GCD of the original pair, to form a pair of relative prime numbers
use the above pair as slope to create new Line object. Note the starting point is fixed which is points[i]
3. use line object as key, store the list of points, e.g. points[j] as value in a hash table, see below for implementation on Line class' hasCode() and equals() methods
4. update the max
https://leetcode.com/discuss/9929/a-java-solution-with-notes
I think check if (gcd!=0) is redundant because the only possibility is x==0&&y==0, which is already handled before.
http://bangbingsyb.blogspot.com/2014/11/leetcode-max-points-on-line.html
1. 如何判断共线?
两点成一直线，所以两点没有共线不共线之说。对于点p1(x1, y1)，p2(x2, y2)，p3(x3, y3)来说，共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同，即
(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)
所以对共线的n点，其中任意两点连线的斜率相同。
2. 如何判断最多的共线点?
对于每个点p出发，计算该点到所有其他点qi的斜率，对每个斜率统计有多少个点符合。其中最多的个数加1（出发点本身）即为最多的共线点。
3. 特殊情况
当x1 = x2，y1!=y2时，为垂直连线。计算斜率时分母为0会出错。
当x1 = x2，y1 = y2时，两点重合。则(x2, y2)和所有(x1, y1)的连线共线。
http://segmentfault.com/a/1190000003904387
时间 O(N^2) 空间 O(N)
http://www.jiuzhang.com/solutions/max-points-on-a-line/
// reuse the hashmap and clear it before reuse.
clear -> O(n)
The relation between normal cases, vertical cases and duplicate cases can be shown as follows:
http://akalius.iteye.com/blog/161852
方法一：用上三角矩阵，矩阵里的值为任意两点的斜率，上三角矩阵用数组a[0..n(n-1)/2]表示。问题就转化为求数组中相同数最多的并且有公共点的数，方法参照“[微软面试题]请把一个整形数组中重复的数字去掉”。
时间复杂度0(n^2)
方法二：平面上N个点以及这N个点构成的无向图，边数n(n-1)/2，对图遍历（深度或广度），遍历到某个点node的时候，计算该点与它的前一个点的斜率r，用pr存储前一个点与它的前结点的斜率，如果pr！=r，则返回到node，继续遍历node的下一条边，如果斜率相等，则count++。如果找不到，则从一下结点开始遍历未访问过的节点。
时间复杂度0(n^2)
http://blog.csdn.net/ojshilu/article/details/21618675
http://myprogrammingpractices.blogspot.com/2015/06/from-mitbbs-facebooklinkedin-google.html
1.max point on line/ (如何不是整数坐标如何处理，需要改写hashmap的compare）
X. Use long as the key(slope)
http://leetcode0.blogspot.com/2013/12/max-points-on-line.html
1: round a double data, 可以用下面的代码：
double slope = 2.1234567;
slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_UP).doubleValue();
System.out.println(slope);
打印的结果是 2.12346
2： 在leetcode中，也可以在class的前面，加入import 语句。
3： 如何遍历一个HashMap
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
First, DO NOT use
Second,
You can use
当计算斜率的时候， long / long 的结果是 long 的， 而不是double的， 因此，要想 得到小数的结果， 需要把一个先转换成double类型，
// slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_DOWN)
// .doubleValue();// round the slope
把这句话注释掉，就可以了。 ~~~~~~~加上这句话， 运行时间，变成了10倍多。
~~~~~~~~可是，不是说double不能完全一样的值吗？？？？？？？？？？？
嗯，出现问题了， 去掉这句话之后， 出现 -0.0 和0.0 的slope不一样的问题。怎么办？？？？
解决方法就是： 把double的slope * 10000, 转换成long 类型，就行了。
没有去遍历map，而直接是在建立的时候，查询并保存了结果。
错误2 ： 2遍都有这个错误。
另外， 在update maxPointOnLine 的时候， 不能把 maxPointOnLine 放到for ( int j) 这个循环的里边， 会导致 update的时候， count 和 nDuplicate 不同时是最大的。 因此，要放到外边去。里层循环， 记录斜率的maxCount .
http://www.jiuzhang.com/solutions/max-points-on-a-line/
Naive Solution:
For every two points i, and j, that form a line, the condition of the third point , say k, lie on the same line is they share the same slope, i.e,
(p_k.y - p_i.y ) (p_j.y - p_i.y)
------------------- = -------------------
(p_k.x - p_i.x) (p_j.x - p_i.x)
which is equal to:
(p_k.y - p_i.y) * (p_j.x - p_i.x) = (p_j.y - p_i.y) * (p_k.x - p_i.x)
There is one corner case that all points are the same. If in this case, the result is length of the points array.
Another tricky point to note is that for points (0,0), (1,1) (0,0), the max number of points are expected to be 3, not 2. So in the inner loop, we don't need to check if k resides in the same points as i and j.
1. max, localMax should be initialized as 1. That is because if there is only one point in the input array, the result should be 1, instead of 0.
2. samePoints should be initialized as 0. That is because for the input (0,0), (0,0).
Since localMax and samePoints then are 1. The result is 2. If samePoints are initialized with 1, then the result would be 3.
3. When we calculate the slope, do remember to cast it as double, else it will be integer / integer, and generate the wrong result. This is really a error prone point.
At last, the time complexity of this approach is O(n^2) and the space complexity is O(n).
X. Don't use map - brute force
https://discuss.leetcode.com/topic/27745/11ms-java-solution-without-any-map-structure
https://discuss.leetcode.com/topic/6398/solution-in-java-without-hashing-and-floats
use map structure is O(n^2), your sollution is O(n^3).
https://discuss.leetcode.com/topic/32255/java-solution-with-no-double-if-you-are-concerned-with-using-doubles-floats-fear-not-there-is-a-way-around
https://discuss.leetcode.com/topic/874/does-anyone-use-the-idea-of-hough-transform-o-n
https://www.quora.com/What-is-the-greatest-common-divisor-of-0-and-5-or-any-non-zero-no
If a is a non-zero integer, then gcd(a,0)=a
Reason:
a divides both 0 and a(so it is a divisor)
If d divides both 0 and a, then d<=a
(so it is the greatest divisor)
Read full article from 水中的鱼: [LeetCode] Max Points on a Line, Solution
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
http://yucoding.blogspot.com/2013/12/leetcode-question-max-points-on-line.html
First of all, how to know the points are on the same line? The slope!
The slope of a line can be computed using any two points (x1,y1) (x2,y2) on the line:
slop = (y2-y1)/(x2-x1) , x2!=x1.
X. Map<Pair<X,Y>, Integer>
http://blueocean-penn.blogspot.com/2015/01/find-straight-line-with-maximum-points.html
This problem tests our knowledge about two concepts: 1) relative prime or calculate GCD; 2) how hash table works, if we override equals(), we must override hashCode(). Again two simple and fundamental knowledges can solve this seemingly complex problems.
The algorithm has those steps:
Given list of n points, saying points[k] where k = 0, 1, ..., n-1
max: the maximum number of points on a line
1. for each point points[i], loop through any other points in the list points[j], where j!=i
2. representing the slope of the line by calculating a pair of numbers, (points[j].y-points[i].y, points[j].x-points[i].x)
if(points[j].x-points[i].x==0) which is a vertical line, then form a pair of numbers (1, 0)
else then divided by the GCD of the original pair, to form a pair of relative prime numbers
use the above pair as slope to create new Line object. Note the starting point is fixed which is points[i]
3. use line object as key, store the list of points, e.g. points[j] as value in a hash table, see below for implementation on Line class' hasCode() and equals() methods
4. update the max
/*line class using pair of relative prime numbers
*to represent the line from a pair of points
*/
static class Line {
int dx, dy;
public Line(int x, int y){
if(x==0){//take care of vertical line
dx = 0; dy = 1;
} else {
int g = gcd(x, y);
dx = x/g;
dy = y/g;
if(dy<0){//this will make sure (-1, -1) and (1, 1) maps to the same line
dy = dy*-1; dx = dx*-1;
}
}
}
@Override
public int hashCode(){
return dx*31+dy;
}
@Override
public boolean equals(Object line){
if(line == this)
return true;
if(line instanceof Line){
return this.dx == ((Line)line).dx && this.dy == ((Line)line).dy;
}
return false;
}
public static int gcd(int x, int y){
if(y==0)
return x;
x = Math.abs(x);
y = Math.abs(y);
int r = 0;
for(; (r=x%y)!=0; x=y, y=r){}
return y;
}
}
static class Point{
int x, y;
public Point(int x, int y){this.x = x; this.y = y;}
}
/*
* code loop through each points with any other points, and form a line object, store the line
* and associated points in a hashtable,
* the line is defined as pair of relative prime (p1.x-p.x, p1.y-p.y)
*/
static Set<Point> findMaxPointsLine(Point[] points){
int max = Integer.MAX_VALUE;
Line maxLine = null;
Set<Point> maxPoints = new HashSet<Point>();
for(int i=0; i<points.length; i++){
//map store all of the lines go through points[i] and its associated points on the line,
//besides the points[i] itself
Map<Line, HashSet<Point>> myLines = new HashMap<Line, HashSet<Point>>();
for(int j=0; j!=i && j<points.length; j++){
Line line = new Line(points[j].x - points[i].x, points[j].y - points[j].y);
if(!myLines.containsKey(line)){
HashSet<Point> set = new HashSet<Point>();
set.add(points[j]);
myLines.put(line, set);
}else{
myLines.get(line).add(points[j]);
}
if(myLines.get(line).size()>max){
max = myLines.get(line).size();
maxLine = line;
}
}
// add point[i] itself
myLines.get(maxLine).add(points[i]);
maxPoints = myLines.get(maxLine);
}
return maxPoints;
}
http://www.geeksforgeeks.org/count-maximum-points-on-same-line/// method to find maximum colinear pointint maxPointOnSameLine(vector< pair<int, int> > points){ int N = points.size(); if (N < 2) return N; int maxPoint = 0; int curMax, overlapPoints, verticalPoints; // map to store slope pair unordered_map<pair<int, int>, int> slopeMap; // looping for each point for (int i = 0; i < N; i++) { curMax = overlapPoints = verticalPoints = 0; // looping from i + 1 to ignore same pair again for (int j = i + 1; j < N; j++) { // If both point are equal then just // increase overlapPoint count if (points[i] == points[j]) overlapPoints++; // If x co-ordinate is same, then both // point are vertical to each other else if (points[i].first == points[j].first) verticalPoints++; else { int yDif = points[j].second - points[i].second; int xDif = points[j].first - points[i].first; int g = __gcd(xDif, yDif); // reducing the difference by their gcd yDif /= g; xDif /= g; // increasing the frequency of current slope // in map slopeMap[make_pair(yDif, xDif)]++; curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]); } curMax = max(curMax, verticalPoints); } // updating global maximum by current point's maximum maxPoint = max(maxPoint, curMax + overlapPoints + 1); // printf("maximum colinear point which contains current // point are : %d\n", curMax + overlapPoints + 1); slopeMap.clear(); } return maxPoint;}I think check if (gcd!=0) is redundant because the only possibility is x==0&&y==0, which is already handled before.
* A line is determined by two factors,say y=ax+b
*
* If two points(x1,y1) (x2,y2) are on the same line(Of course).
* Consider the gap between two points.
* We have (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) a is a rational, b is canceled since b is a constant
* If a third point (x3,y3) are on the same line. So we must have y3=ax3+b
* Thus,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
* Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
* So we can use y0&x0 to track a line;http://bangbingsyb.blogspot.com/2014/11/leetcode-max-points-on-line.html
1. 如何判断共线?
两点成一直线，所以两点没有共线不共线之说。对于点p1(x1, y1)，p2(x2, y2)，p3(x3, y3)来说，共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同，即
(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)
所以对共线的n点，其中任意两点连线的斜率相同。
2. 如何判断最多的共线点?
对于每个点p出发，计算该点到所有其他点qi的斜率，对每个斜率统计有多少个点符合。其中最多的个数加1（出发点本身）即为最多的共线点。
3. 特殊情况
当x1 = x2，y1!=y2时，为垂直连线。计算斜率时分母为0会出错。
当x1 = x2，y1 = y2时，两点重合。则(x2, y2)和所有(x1, y1)的连线共线。
http://segmentfault.com/a/1190000003904387
时间 O(N^2) 空间 O(N)
一个点加一个斜率，就可以唯一的确定一条直线。所以我们对每个点，都计算一下该点和其他点连线的斜率，这样对于这个点来说，相同斜率的直线有多少条，就意味着有多少个点在同一条直线上，因为这些直线是相同的。另外，如果计算过点A和点B的直线，当算到点B时，就不用再和A连线了，因为AB这条直线上的点数已经都计算过了。这里，我们用哈希表，以斜率为key，记录有多少重复直线。
哈希表的Key为Double，但Double是可以有正0和负0的，而且不一样。所以我们要用
==>
if(slope * slope == 0) slope = 0;把负0都变成正0==>
public int maxPoints(Point[] points) {
if(points.length <= 1) return points.length;
int max = Integer.MIN_VALUE;
for(int i = 0; i < points.length; i++){
//过当前点的直线组成的哈希表，斜率为key
HashMap<Double, Integer> lines = new HashMap<Double, Integer>();
int vertical = 0, same = 1, currMax = 0;
for(int j = i + 1; j < points.length; j++){
// 统计相同的点
if(points[i].x == points[j].x && points[i].y == points[j].y){
same++;
continue;
}
// 统计斜率为无穷的点，他们都在一条直线上
if(points[i].x == points[j].x){
vertical++;
continue;
}
// 计算连线的斜率
double slope = ((double)points[i].y - (double)points[j].y) / ((double)points[i].x - (double)points[j].x);
// 修正负0
if(slope * slope == 0) slope = 0;
lines.put(slope, lines.containsKey(slope) ? lines.get(slope) + 1 : 1);
currMax = Math.max(currMax, lines.get(slope));
}
// 经过该点的直线上最多的点数，我们在无穷斜率和正常斜率中选较大的，还要加上相同的点数
currMax = Math.max(vertical, currMax) + same;
max = Math.max(currMax, max);
}
return max;
}// reuse the hashmap and clear it before reuse.
clear -> O(n)
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
public int maxPoints(Point[] points) { if (points == null || points.length == 0) { return 0; } HashMap<Double, Integer> map=new HashMap<Double, Integer>(); int max = 1; for(int i = 0 ; i < points.length; i++) { // shared point changed, map should be cleared and server the new point map.clear(); // maybe all points contained in the list are same points,and same points' k is // represented by Integer.MIN_VALUE map.put((double)Integer.MIN_VALUE, 1); int dup = 0; for(int j = i + 1; j < points.length; j++) { if (points[j].x == points[i].x && points[j].y == points[i].y) { dup++; continue; } // look 0.0+(double)(points[j].y-points[i].y)/(double)(points[j].x-points[i].x) // because (double)0/-1 is -0.0, so we should use 0.0+-0.0=0.0 to solve 0.0 !=-0.0 // problem // if the line through two points are parallel to y coordinator, then K(slop) is // Integer.MAX_VALUE double key=points[j].x - points[i].x == 0 ? Integer.MAX_VALUE : 0.0 + (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x); if (map.containsKey(key)) { map.put(key, map.get(key) + 1); } else { map.put(key, 2); } } for (int temp: map.values()) { // duplicate may exist if (temp + dup > max) { max = temp + dup; } } } return max; } }http://www.programcreek.com/2014/04/leetcode-max-points-on-a-line-java/
The relation between normal cases, vertical cases and duplicate cases can be shown as follows:
public int maxPoints(Point[] points) { if(points == null || points.length == 0) return 0; HashMap<Double, Integer> result = new HashMap<Double, Integer>(); int max=0; for(int i=0; i<points.length; i++){ int duplicate = 1;// int vertical = 0; for(int j=i+1; j<points.length; j++){ // j should start from 0(&&j!=i) or i+1? //handle duplicates and vertical if(points[i].x == points[j].x){ if(points[i].y == points[j].y){ duplicate++; }else{ vertical++; } }else{ double slope = points[j].y == points[i].y ? 0.0 : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x); if(result.get(slope) != null){ result.put(slope, result.get(slope) + 1); }else{ result.put(slope, 1); } } } for(Integer count: result.values()){ if(count+duplicate > max){ max = count+duplicate; } } max = Math.max(vertical + duplicate, max); result.clear(); } return max; } |
方法一：用上三角矩阵，矩阵里的值为任意两点的斜率，上三角矩阵用数组a[0..n(n-1)/2]表示。问题就转化为求数组中相同数最多的并且有公共点的数，方法参照“[微软面试题]请把一个整形数组中重复的数字去掉”。
时间复杂度0(n^2)
方法二：平面上N个点以及这N个点构成的无向图，边数n(n-1)/2，对图遍历（深度或广度），遍历到某个点node的时候，计算该点与它的前一个点的斜率r，用pr存储前一个点与它的前结点的斜率，如果pr！=r，则返回到node，继续遍历node的下一条边，如果斜率相等，则count++。如果找不到，则从一下结点开始遍历未访问过的节点。
时间复杂度0(n^2)
http://blog.csdn.net/ojshilu/article/details/21618675
http://myprogrammingpractices.blogspot.com/2015/06/from-mitbbs-facebooklinkedin-google.html
1.max point on line/ (如何不是整数坐标如何处理，需要改写hashmap的compare）
X. Use long as the key(slope)
http://leetcode0.blogspot.com/2013/12/max-points-on-line.html
1: round a double data, 可以用下面的代码：
double slope = 2.1234567;
slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_UP).doubleValue();
System.out.println(slope);
打印的结果是 2.12346
2： 在leetcode中，也可以在class的前面，加入import 语句。
3： 如何遍历一个HashMap
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
First, DO NOT use
double in such kind of problem, you don't need them and they will make you suffer, DO use integersSecond,
<k, b> is not a good idea simply because you cannot represent all the possible line using it.You can use
<a, b, c> to represent all the possible line, i.e., ax + by + c = 0 where a, b, c are all integers.当计算斜率的时候， long / long 的结果是 long 的， 而不是double的， 因此，要想 得到小数的结果， 需要把一个先转换成double类型，
public int maxPoints(Point[] points) { // for each point, we calculate its slope with others, // if they are the same, we save them into a Hashtable if (points.length <= 1) { // pay attention to length == 1 return points.length; } int nMaxPoints = 0; for (int i = 0; i < points.length - 1; i++) { // for slope Double, we map its count of integers that could form // this slope with points[i] Map<Long, Integer> map = new HashMap<Long, Integer>(); Point pLeft = points[i]; int nDuplicate = 1; // how many points that having the same (x,y) // value with pLeft(inclusive) for (int j = i + 1; j < points.length; j++) { Point pRight = points[j]; if (pLeft.x == pRight.x && pLeft.y == pRight.y) { nDuplicate++; continue; } else { Long longSlope; // is is 10000* actuall slope // calculate their slope and save into a the HashMap if (pLeft.x == pRight.x) { longSlope = Long.MAX_VALUE; } else { double slope = (double) (pRight.y - pLeft.y) / (pRight.x - pLeft.x);// slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_DOWN)// .doubleValue();// round the slope longSlope =Math.round(slope*10000); } // insert the slope into the hashMap Integer objCount = map.get(longSlope); if (objCount == null) { map.put(longSlope, 1); } else { map.put(longSlope, objCount + 1); } } }// enf of for loop ---- j nMaxPoints = Math.max(nMaxPoints, nDuplicate); // in case that // HashMap is empty // search all slopes passing pLeft, and update the nMaxPoints Iterator<Entry<Long, Integer>> iter = map.entrySet().iterator(); while (iter.hasNext()) { // for each slope, need find the max point Map.Entry<Long, Integer> entry = (Map.Entry<Long, Integer>) iter.next(); Integer curCount = (Integer) entry.getValue(); nMaxPoints = Math.max(nMaxPoints, curCount + nDuplicate); } // end of while } // end of for loop ----- ivalue return nMaxPoints; }// .doubleValue();// round the slope
把这句话注释掉，就可以了。 ~~~~~~~加上这句话， 运行时间，变成了10倍多。
~~~~~~~~可是，不是说double不能完全一样的值吗？？？？？？？？？？？
嗯，出现问题了， 去掉这句话之后， 出现 -0.0 和0.0 的slope不一样的问题。怎么办？？？？
解决方法就是： 把double的slope * 10000, 转换成long 类型，就行了。
没有去遍历map，而直接是在建立的时候，查询并保存了结果。
public int maxPoints(Point[] points) { if (points.length <= 1) return points.length; int maxPointOnLine = 0; HashMap<Long, Integer> map = new HashMap<Long, Integer>();// map scale to count for (int i = 0; i < points.length; i++) { map.clear(); int duplicate = 1; int maxCount = 0; for (int j = i + 1; j < points.length; j++) { Long ratio = 0L; if (points[j].x == points[i].x && points[j].y == points[i].y) { duplicate++; } else { if (points[j].x == points[i].x) ratio = Long.MAX_VALUE; else ratio = (long) ( (double)(points[j].y - points[i].y) / (points[j].x - points[i].x) * 100000); int count =1; if (map.get(ratio) != null) count = map.get(ratio) +1; map.put(ratio, count); maxCount = Math.max(maxCount, count); } } maxPointOnLine = Math.max(maxPointOnLine, duplicate + maxCount); } return maxPointOnLine; }另外， 在update maxPointOnLine 的时候， 不能把 maxPointOnLine 放到for ( int j) 这个循环的里边， 会导致 update的时候， count 和 nDuplicate 不同时是最大的。 因此，要放到外边去。里层循环， 记录斜率的maxCount .
http://www.jiuzhang.com/solutions/max-points-on-a-line/
class Line { public double a, b, c; public Line(double a, double b, double c) { this.a = a; this.b = b; this.c = c; } public Line(int x1, int y1, int x2, int y2) { if (x1 == x2) { if (x1 == 0) { a = 1; b = 0; c = 0; } else { a = 1.0 / x1; b = 0; c = 1; } } else if (y1 == y2) { if (y1 == 0) { a = 0; b = 1; c = 0; } else { a = 0; b = 1.0 / y1; c = 1; } } else { if (x1 * y2 == x2 * y1) { a = 1; b = - 1.0 * (y1 - y2) / (x1 - x2); c = 0; } else { a = 1.0 * (y1 - y2) / (x2 * y1 - x1 * y2); b = 1.0 * (x1 - x2) / (x1 * y2 - x2 * y1); c = 1; } } } public String toString() { return Double.toString(a) + " " + Double.toString(b) + " " + Double.toString(c); } } public class Solution { public int maxPoints(Point[] points) { if (points.length < 2) { return points.length; } HashMap<String, Integer> hash = new HashMap<String, Integer>(); for (int i = 0; i < points.length; i++) { for (int j = i + 1; j < points.length; j++) { Line line = new Line(points[i].x, points[i].y, points[j].x, points[j].y); String key = line.toString(); if (hash.containsKey(key)) { hash.put(key, hash.get(key) + 1); } else { hash.put(key, 1); } } } int max = 0; String maxKey = ""; for (String key: hash.keySet()) { if (hash.get(key) > max) { max = hash.get(key); maxKey = key; } } String[] params = maxKey.split(" "); double a = Double.parseDouble(params[0]); double b = Double.parseDouble(params[1]); double c = Double.parseDouble(params[2]); int count = 0; for (int i = 0; i < points.length; i++) { if (Math.abs(a * points[i].x + b * points[i].y - c) < 1e-6) { count++; } } return count; }http://buttercola.blogspot.com/2014/10/leetcode-max-points-on-line.html
Naive Solution:
For every two points i, and j, that form a line, the condition of the third point , say k, lie on the same line is they share the same slope, i.e,
(p_k.y - p_i.y ) (p_j.y - p_i.y)
------------------- = -------------------
(p_k.x - p_i.x) (p_j.x - p_i.x)
which is equal to:
(p_k.y - p_i.y) * (p_j.x - p_i.x) = (p_j.y - p_i.y) * (p_k.x - p_i.x)
There is one corner case that all points are the same. If in this case, the result is length of the points array.
Another tricky point to note is that for points (0,0), (1,1) (0,0), the max number of points are expected to be 3, not 2. So in the inner loop, we don't need to check if k resides in the same points as i and j.
1. max, localMax should be initialized as 1. That is because if there is only one point in the input array, the result should be 1, instead of 0.
2. samePoints should be initialized as 0. That is because for the input (0,0), (0,0).
Since localMax and samePoints then are 1. The result is 2. If samePoints are initialized with 1, then the result would be 3.
3. When we calculate the slope, do remember to cast it as double, else it will be integer / integer, and generate the wrong result. This is really a error prone point.
At last, the time complexity of this approach is O(n^2) and the space complexity is O(n).
public int maxPoints(Point[] points) { if (points == null || points.length == 0) { return 0; } int max = 1; for (int i = 0; i < points.length - 1; i++) { Map<Double, Integer> map = new HashMap<Double, Integer>(); int samePoints = 0; double slope = 0; int localMax = 1; for (int j = i + 1; j < points.length; j++) { // check if point i and j are the same if (points[i].x == points[j].x && points[i].y == points[j].y) { samePoints++; continue; } else if (points[i].y == points[j].y) { slope = 0.0; } else if (points[i].x == points[j].x) { slope = (double) Integer.MAX_VALUE; } else { slope = (double) (points[j].y - points[i].y) / (points[j].x - points[i].x); } if (map.containsKey(slope)) { map.put(slope, map.get(slope) + 1); } else { map.put(slope, 2); } } for (Integer num : map.values()) { // Track max during previous for loop localMax = Math.max(localMax, num); } localMax += samePoints; max = Math.max(max, localMax); } return max; }X. Don't use map - brute force
https://discuss.leetcode.com/topic/27745/11ms-java-solution-without-any-map-structure
https://discuss.leetcode.com/topic/6398/solution-in-java-without-hashing-and-floats
use map structure is O(n^2), your sollution is O(n^3).
public int maxPoints(Point[] points){
if(points == null || points.length == 0){
return 0;
}
if(points.length <= 2){
return points.length;
}
int ret = 0;
int n = points.length;
int count = 0;
int duplicates = 0;
for(int i = 0; i < n; i++){
Point p = points[i];
count = 0;
duplicates = 0;
for(int j = i + 1; j < n; j++){
Point q = points[j];
if(q.x == p.x && q.y == p.y){
duplicates++;
ret = Math.max(ret, duplicates + 1);
continue;
}
//count point q
count = 1;
for(int k = j + 1; k < n; k++){
Point r = points[k];
count += isCoLinear(p, q, r)? 1: 0;
}
//count point p
ret = Math.max(ret, count + duplicates + 1);
}
}
return ret;
}
private boolean isCoLinear(Point p, Point q, Point r){
int val = (q.y - p.y) *(r.x - q.x) - (r.y - q.y)*(q.x - p.x);
return val == 0;
}
X. Don't use Doublehttps://discuss.leetcode.com/topic/32255/java-solution-with-no-double-if-you-are-concerned-with-using-doubles-floats-fear-not-there-is-a-way-around
This solution is somewhat slower than the standard solution which uses doubles to store slopes. It, however, guarantees that there will not be any precision error, as long as we are dealing with integers as point coordinates.
You can read here about the pairing functions that uniquely represent any pair of integers. https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function
* We can use a pairing function to represent two integers uniquely.
* In our case we use a pairing function to represent a fraction,
* with first integer being the numerator and second integer being the denominator.
* Hence, we avoid precision concerns that may come up if we use floats / doubles.
*/
public int maxPoints(Point[] points) {
if (points.length < 2) return points.length;
int max = 2;
for (Point p1 : points) {
Map<Integer, Integer> slopes = new HashMap<>(points.length);
int localMax = 0;
for (Point p2 : points) {
int num = p2.y - p1.y;
int den = p2.x - p1.x;
// pairing functions only work with non-negative integers
// we store the sign in a separate variable
int sign = 1;
if ((num > 0 && den < 0) || (num < 0 && den > 0)) sign = -1;
num = Math.abs(num);
den = Math.abs(den);
// pairing functions represent a pair of any two integers uniquely;
// they can be used as hash functions for any sequence of integers;
// therefore, a pairing function from 1/2 doesn't equal to that from 3/6
// even though the slope 1/2 and 3/6 is the same.
// => we need to convert each fraction to its simplest form, i.e. 3/6 => 1/2
int gcd = GCD(num, den);
num = gcd == 0 ? num : num / gcd;
den = gcd == 0 ? den : den / gcd;
// We can use Cantor pairing function pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2
// and include the sign
int m = sign * (num + den) * (num + den + 1) / 2 + den;
if (slopes.containsKey(m)) slopes.put(m, slopes.get(m)+1);
else slopes.put(m, 1);
if (m == 0) continue;
localMax = Math.max(slopes.get(m),localMax);
}
max = Math.max(max, localMax + slopes.get(0));
}
return max;
}
public int GCD(int a, int b) {
if (b == 0) return a;
return GCD(b,a % b);
}https://discuss.leetcode.com/topic/874/does-anyone-use-the-idea-of-hough-transform-o-n
https://www.quora.com/What-is-the-greatest-common-divisor-of-0-and-5-or-any-non-zero-no
If a is a non-zero integer, then gcd(a,0)=a
Reason:
a divides both 0 and a(so it is a divisor)
If d divides both 0 and a, then d<=a
(so it is the greatest divisor)
Read full article from 水中的鱼: [LeetCode] Max Points on a Line, Solution
