Description
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution
HashMap
- 平面里確定一條直線要兩個數(shù)據(jù)，二維的直線可以用ax + b = y來表示灼捂，那么只需確定a和b就可以得到一條直線趾代。但是這道題這么做不方便殊鞭，表示直線還有其他方式，可以是兩個不同的點(高中數(shù)學做法)诀黍，
也可以是一個點加一個斜率(這道題做法) - 斜率slope = (y2 - y1) / (x2 - x1)，當 x1 == x2 時，分母為0滤港，斜率為無窮，表示和y軸平行的直線們
-
在計算機里使用double表示斜率趴拧，是不嚴謹?shù)囊彩遣徽_的溅漾，double有精度誤差，double是有限的著榴，斜率是無限的添履，無法使用有限的double表示無限的斜率，不過此題的test case沒有涉及這個問題 表示斜率最靠譜的方式是用最簡分數(shù)兄渺，即分子分母都無法再約分了缝龄。分子分母同時除以他們的最大公約數(shù)gcd(Greatest Common Divisor)即可得到最簡分數(shù)- gcd(a,b)汰现，一般求的是兩個正整數(shù)的gcd。這道題a和b有可能是0叔壤，分別表示與x軸或y軸平行的斜率(注意ab不能同時為0,表示同一個點沒有意義)瞎饲，所以這道題我們規(guī)定ab取值范圍：a>=0,b>=0。至于負數(shù)炼绘，先變成正數(shù)取gcd嗅战，再確定最終斜率的正負
- gcd ( a , b )計算：歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計算兩個整數(shù)a,b的最大公約數(shù)俺亮。其計算原理依賴于下面的定理：
gcd(a,b) = gcd(b,a mod b) - 觀察gcd(a,b)驮捍，假設a,b為非負整數(shù)：
-
a和b中有一個為零，那么gcd為另一個不為0的數(shù)脚曾；那么slope一定就會變成"+1/0"东且，在垂直經(jīng)過curr的直線上的所有點斜率都是這個！這樣是不是很好本讥，不用單獨處理斜率為infinite的情況了珊泳。 - a和b都為0，gcd為0拷沸；
-
至于算法也沒什么色查，就是窮舉，對每個點撞芍，都計算一下該點和其他點連線的斜率秧了，這樣對于這個點來說，相同斜率的直線有多少條序无，就意味著有多少個點在同一條直線上验毡，因為這些直線是相同的。另外愉镰，如果計算過點A和點B的直線米罚，當算到點B時，就不用再和A連線了丈探，因為AB這條直線上的點數(shù)已經(jīng)都計算過了录择。這里，我們用哈希表碗降，以斜率為key隘竭，記錄有多少重復直線。
注意如果想要自定義Slope(斜率)類作為HashMap的Key的話要重寫hashCode()和equals()函數(shù)讼渊， 偷懶的話可以把斜率的分數(shù)表示成String作為Key动看，這樣就省了一些事。
hashmap的value的含義應定義為：過cur點以key為斜率的直線有幾個除了cur以外的點爪幻。在算完 過cur的所有直線后菱皆，統(tǒng)計cur點的總個數(shù)howManyCur须误，加到當前點最多的直線上，即可得到含cur點的最大直線上的點數(shù)仇轻。
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
class Solution {
public int maxPoints(Point[] points) {
if (points == null) {
return -1;
}
if (points.length < 2) {
return points.length;
}
int max = 0;
for (int i = 0; i < points.length; ++i) {
Map<String, Integer> slope2Count = new HashMap<>();
Point curr = points[i];
int imax = 0;
int currCount = 1;
for (int j = i + 1; j < points.length; ++j) {
Point q = points[j];
// same point with curr
if (q.x == curr.x && q.y == curr.y) {
++currCount;
continue;
}
// different point
String slope = getSlope(curr, q);
slope2Count.put(slope, slope2Count.getOrDefault(slope, 0) + 1);
imax = Math.max(slope2Count.get(slope), imax);
}
// don't forget to add the count of same point
max = Math.max(imax + currCount, max);
}
return max;
}
// return slope as string for convenient
private String getSlope(Point p, Point q) {
long a = (long) q.x - p.x;
long b = (long) q.y - p.y;
String sign = getSign(a, b);
a = Math.abs(a);
b = Math.abs(b);
long gcd = getGCD(a, b); // use GCD to avoid losing accuracy
return sign + a / gcd + "/" + b / gcd;
}
// return string sign
private String getSign(long a, long b) {
return (a > 0 && b < 0) || (a < 0 && b > 0) ? "-" : "+";
}
private long getGCD(long a, long b) {
if (b == 0) {
return a;
}
return getGCD(b, a % b);
}
}
