資訊專欄INFORMATION COLUMN
摘要：兩次循環(huán)對中第個和第個進行比較設置重復點數(shù)，相同斜率點數(shù)。內部循環(huán)每次結束后更新和點相同斜率的點的最大數(shù)目。外部循環(huán)每次更新為之前結果和本次循環(huán)所得的較大值。重點一以一個點為參照求其他點連線的斜率，不需要計算斜率。
Problem
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
ExampleGiven 4 points: (1,2), (3,6), (0,0), (1,3).
The maximum number is 3.
建立一個斜率對應point個數(shù)的HashMap。
兩次循環(huán)對points中第i個和第j個進行比較：
設置重復點數(shù)duplicate，相同斜率點數(shù)count。內部循環(huán)每次結束后更新count——和點i相同斜率的點的最大數(shù)目。（點i可能有很多相同斜率點的集合，故內層遍歷完之后取最大的集合的大小。）
外部循環(huán)每次更新res為之前結果和本次循環(huán)所得duplicate+count的較大值。
重點一：以一個點為參照求其他點連線的斜率，不需要計算斜率。
重點二：兩次循環(huán)體現(xiàn)重點一中的相對關系，可以讓j從i開始，節(jié)省時間。
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;
}
}
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://systransis.cn/yun/65473.html
Given n points on a 2D plane,find the maximum number of points that lie on the same straight line. from decimal import Decimal # Definition for a point. class Point: def __init__(self, a=0, b=0)...
摘要：哈希表復雜度時間空間思路一個點加一個斜率，就可以唯一的確定一條直線。這里，我們用哈希表，以斜率為，記錄有多少重復直線。注意哈希表的為，但是可以有正和負的，而且不一樣。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same stra...
摘要：分子分母同時除以他們的最大公約數(shù)即可得到最簡分數(shù)，一般求的是兩個正整數(shù)的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時為表示同一個點沒有意義，所以這道題我們規(guī)定取值范圍。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the s...
Problem Youre now a baseball game point recorder. Given a list of strings, each string can be one of the 4 following types: Integer (one rounds score): Directly represents the number of points you get...
閱讀 1565·2021-11-25 09:43
閱讀 2349·2019-08-30 15:55
閱讀 1474·2019-08-30 13:08
閱讀 2687·2019-08-29 10:59
閱讀 825·2019-08-29 10:54
閱讀 1597·2019-08-26 18:26
閱讀 2559·2019-08-26 13:44
閱讀 2663·2019-08-23 18:36
