Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
A:
现在的思路，就是，先根据slope 分组， 具有相同(很接近）斜率 slope的点放到一组。
然后，对每一组， 再找出具有相同(很接近） 的截距（intersect）的点来。 --记录最大的list的长度，然后返回即可。--------------理论上来讲，是O(n^2)
注意： 重复的点，也算不同的点来count
哎，就TM知道， 不能用这种屌丝办法，会超时， 现在好了，真的超时了。废了一晚上的时间。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~主要的时间开销，就在Step1 里的双重循环上了。（对每个点，找它的所有的slope），其目的是： 将具有same slope 的组合 放到一起。（虽然，可能不是相同的节点）
-----------------------------------------代码见本页最后--------------------------------
----------------其实，不是算法复杂度的问题， 是利用了O(n^2)的空间的问题。 也存储了太多的，冗余的slope。------------------------
--------------------------下面是别人的思路-------------------------------------------------
分析：首先要注意的是，输入数组中可能有重复的点。由于两点确定一条直线，一个很直观的解法是计算每两个点形成的直线，然后把相同的直线合并，最后 包含点最多的直线上点的个数就是本题的解。我们知道表示一条直线可以用斜率和y截距两个浮点数（垂直于x轴的直线斜率为无穷大，截距用x截距），同时还需 要保存每条直线上的点（避免重复）。听起来就很麻烦，但是基于这个思想有一种简单的实现方式：
- 以某点O为中心，计算它和其他点的斜率，如果有两个点A、B和O点形成的斜率相等，那么ABO三点是共线的，如果有多个点和O的斜率相等，那么这 多个点和O也是共线的，因此我们可以求出包含O的所有直线中点数最多的直线，会得到一个最大共线点数k(O)，如果和O点重复的点有n个（除了O本身）， 那么K(O) = K(O) + n。这一步的计算中，为了提高效率，我们可以用哈希表来保存某个斜率对应的点的数目。
- 对数组中的每一个点i，按照第一步计算得到每个点最大点数K(i)
- 从k(i)中选取最大的就是本题的解
- 注意：为了避免重复计算，以数组中第i个点为中心时，只计算数组中它右边的所有点
public class MaxPointsOnALine2 {
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;
}
}
罪魁祸首找到啦~~~~~~~~~~~~~~， 就是
// 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 类型，就行了。
因此，方法一，也如此解决pass。 具体修改，可以见Eclipse中的代码。 （而且，上面的代码，也没有处理duplicates 的问题。 因此，还是只看解法2吧。
Mistakes:
1： 刚开始，没有考虑，输入数组的长度为0， 为1 的情况。 反而在题目中，直接默认为长度超过2了。 直接调用了， slopeList[0] 啊什么的
2:： 对于slope 为正无穷的情况， 在求 difference of intersect的时候，要要单独处理， 其各自的intersect 可以用point.x 的值代替。
3： 注意： 重复的点，也算不同的点来count。 但是，在实际
4： 一开始，设
double minDiff = 0.0000001;
结果太小了，计算机的round error还是超过了这个值。 更改为
double minDiff = 0.00001;
5: 方法二的时候， update nMaxPoints 在第二个for循环后面，而且，刚开始，弄成iter 必须是非空才能update 的。因此，对于输入 ”(0,0)，(0,0)“ 就不能update nMaxPoints了。
Learned:
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();
}
效率高,以后一定要使用此种方式！
3.5------------------另一种方式，更简单 ----------------
HashMap<Integer,Integer> map = new HashSet<Integer,Integer>();
for(int key : map.keySet()
// do something
4： 表示直线，
First, DO NOT use
Second,
You can use
Big Mistake:
当计算斜率的时候， long / long 的结果是 long 的， 而不是double的， 因此，要想 得到小数的结果， 需要把一个先转换成double类型， 我艹~~~~~~~~~~~~~~~~~~~ 你SB，~~~~~脑子坏掉了。 Tiger
错误2 ： 2遍都有这个错误。
另外， 在update maxPointOnLine 的时候， 不能把 maxPointOnLine 放到for ( int j) 这个循环的里边， 会导致 update的时候， count 和 nDuplicate 不同时是最大的。 因此，要放到外边去。里层循环， 记录斜率的maxCount .
哎，Tiger，先不要节省代码行数， 即使超出30行又能如何？ 要保证正确才对。
错误3：
曾经写过这样 count = （map.get(key) == null)? 0 : map.get(key) + 1 ; 这样的结果不是预期的。 不知道为什么 ~~~~~~~~
--------------------------------解法1 的代码（没pass，只代表思路）----------------------
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.--------------------------------------------第二遍-----------------------------------------
没有去遍历map，而直接是在建立的时候，查询并保存了结果。Big Mistake:
当计算斜率的时候， long / long 的结果是 long 的， 而不是double的， 因此，要想 得到小数的结果， 需要把一个先转换成double类型， 我艹~~~~~~~~~~~~~~~~~~~ 你SB，~~~~~脑子坏掉了。 Tiger
import java.util.*;
public class Solution {
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;
}
}
错误2 ： 2遍都有这个错误。
另外， 在update maxPointOnLine 的时候， 不能把 maxPointOnLine 放到for ( int j) 这个循环的里边， 会导致 update的时候， count 和 nDuplicate 不同时是最大的。 因此，要放到外边去。里层循环， 记录斜率的maxCount .
哎，Tiger，先不要节省代码行数， 即使超出30行又能如何？ 要保证正确才对。
错误3：
曾经写过这样 count = （map.get(key) == null)? 0 : map.get(key) + 1 ; 这样的结果不是预期的。 不知道为什么 ~~~~~~~~
--------------------------------解法1 的代码（没pass，只代表思路）----------------------
import java.math.BigDecimal;
import java.util.Map;
import java.util.Map.Entry;
public class Solution {
public int maxPoints(Point[] points) {
// first divided by slope,
// NOTE: due to the fact that digital numbers cannot be too concise, we
// use approximatin
if (points == null || points.length == 0)
return 0;
if (points.length == 1)
return 1;
double minDiff = 0.00001;
Map<Double, Integer> map = new HashMap<Double, Integer>();
// a map from slope into the position of List of Points
ArrayList<HashSet<Point>> slopeList = new ArrayList<HashSet<Point>>();
// Step1: for each pair of points, calculte their slope and add them
// into the hashMap
for (int i = 0; i < points.length - 1; i++) {
for (int j = i + 1; j < points.length; j++) {
Point pLeft = points[i].x < points[j].x ? points[i] : points[j];
Point pRight = points[i].x >= points[j].x ? points[i] : points[j];
double slope;
if (pRight.x - pLeft.x == 0) {
slope = Double.MAX_VALUE;
} else {
slope =( (double)(pRight.y - pLeft.y)) / (pRight.x - pLeft.x);
slope = BigDecimal.valueOf(slope).setScale(5, BigDecimal.ROUND_HALF_DOWN)
.doubleValue();// round the slope
}
Integer index = map.get(slope);
if (index == null) { // if current slope is not found
index = slopeList.size();
map.put(slope, slopeList.size()); // add at last position
HashSet<Point> tmp = new HashSet<Point>();
slopeList.add(tmp); // add one element at slopeList
}
HashSet<Point> tmpSet = slopeList.get(index);
tmpSet.add(pLeft);
tmpSet.add(pRight);
}
}
// Step 2: now all list contains points of same slope, with some of
// its neighgbors,
// we try to find , if using same slope, check the intersect difference
int maxPoints = 0;
Iterator<Entry<Double, Integer>> iter = map.entrySet().iterator();
while (iter.hasNext()) { // for each slope, need find the max point
// through a line ,coz they might parrelel
Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>) iter.next();
Double slope = (Double) entry.getKey();
Integer index = (Integer) entry.getValue();
HashSet<Point> curSet = slopeList.get(index);
if (curSet.size() <= maxPoints) {
continue;
}
// each element contains lists that having same slope and intersect
ArrayList<ArrayList<Point>> all = new ArrayList<ArrayList<Point>>();
for (Point eachPoint : curSet) { // check the difference with
// existing ones
boolean findGroup = false;
// check all points in the list, that might belongs to same
// group
for (int j = 0; j < all.size(); j++) {
// if found the node that with intercept small enough
// arraylist, with same slope and same intersect
ArrayList<Point> al = all.get(j);
double curIntercept, newIntersect;
if (slope == Double.MAX_VALUE) {
curIntercept = al.get(0).x;
newIntersect = eachPoint.x;
} else {
curIntercept = al.get(0).y - slope * al.get(0).x;
newIntersect = eachPoint.y - slope * eachPoint.x;
}
if (Math.abs(curIntercept - newIntersect) < minDiff) {
al.add(eachPoint);
findGroup = true;
break;
}
}
// if not find its group, we append this point to all
if (findGroup == false) {
ArrayList<Point> al = new ArrayList<Point>();
al.add(eachPoint);
all.add(al);
}
}
// find the maximun number of List, for current slope,
for (int i = 0; i < all.size(); i++) {
ArrayList<Point> al = all.get(i);
if (al.size() > maxPoints) {
maxPoints = al.size();
}
}
}
return maxPoints;
}
}