[LintCode] Max Points on a Line
1590 ワード
Problem
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example
Given 4 points: (1,2), (3,6), (0,0), (1,3).The maximum number is 3.
Note
傾きがpoint個数に対応するHashMapを作成します.2回のループはpointsのi番目とj番目を比較します.重複点数duplicateを設定し、同じ傾き点数countを設定します.内部ループが終了するたびにcountが更新される--点iと同じ傾きの点の最大数.(点iは同じ傾きの点の集合が多い可能性があるので、内層が遍歴した後に最大の集合の大きさをとる.)外部サイクルがresを更新するたびに、以前の結果と今回のサイクルで得られたduplicate+countの大きな値になります.ポイント1:1つの点を参照して他の点連線の傾きを求め、傾きを計算する必要はありません.ポイント2:2回のサイクルはポイント1の相対関係を体現し、jをiから始め、時間を節約することができる.
Solution
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example
Given 4 points: (1,2), (3,6), (0,0), (1,3).The maximum number is 3.
Note
傾きがpoint個数に対応するHashMapを作成します.2回のループはpointsのi番目とj番目を比較します.重複点数duplicateを設定し、同じ傾き点数countを設定します.内部ループが終了するたびにcountが更新される--点iと同じ傾きの点の最大数.(点iは同じ傾きの点の集合が多い可能性があるので、内層が遍歴した後に最大の集合の大きさをとる.)外部サイクルがresを更新するたびに、以前の結果と今回のサイクルで得られたduplicate+countの大きな値になります.ポイント1:1つの点を参照して他の点連線の傾きを求め、傾きを計算する必要はありません.ポイント2:2回のサイクルはポイント1の相対関係を体現し、jをiから始め、時間を節約することができる.
Solution
public class Solution {
public int maxPoints(Point[] points) {
// Write your code here
int res = 0;
if (points == null || points.length == 0) {
return 0;
}
for (int i = 0; i < points.length; i++) {
int count = 0;
int duplicate = 1;
Map map = new HashMap();
Point p = points[i];
for (int j = i; j < points.length; j++) {
Point q = points[j];
if (q == p) continue;
if (q.x == p.x && q.y == p.y) duplicate++;
else {
double s = p.x == q.x ? Double.MAX_VALUE: (double)(p.y-q.y)/(p.x-q.x);
map.put(s, map.containsKey(s) ? map.get(s)+1: 1);
count = Math.max(count, map.get(s));
}
}
res = Math.max(res, count+duplicate);
}
return res;
}
}