資訊專欄INFORMATION COLUMN
摘要：兩次循環(huán)對(duì)中第個(gè)和第個(gè)進(jìn)行比較設(shè)置重復(fù)點(diǎn)數(shù)，相同斜率點(diǎn)數(shù)。內(nèi)部循環(huán)每次結(jié)束后更新和點(diǎn)相同斜率的點(diǎn)的最大數(shù)目。外部循環(huán)每次更新為之前結(jié)果和本次循環(huán)所得的較大值。重點(diǎn)一以一個(gè)點(diǎn)為參照求其他點(diǎn)連線的斜率，不需要計(jì)算斜率。
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.
建立一個(gè)斜率對(duì)應(yīng)point個(gè)數(shù)的HashMap。
兩次循環(huán)對(duì)points中第i個(gè)和第j個(gè)進(jìn)行比較：
設(shè)置重復(fù)點(diǎn)數(shù)duplicate，相同斜率點(diǎn)數(shù)count。內(nèi)部循環(huán)每次結(jié)束后更新count——和點(diǎn)i相同斜率的點(diǎn)的最大數(shù)目。（點(diǎn)i可能有很多相同斜率點(diǎn)的集合，故內(nèi)層遍歷完之后取最大的集合的大小。）
外部循環(huán)每次更新res為之前結(jié)果和本次循環(huán)所得duplicate+count的較大值。
重點(diǎn)一：以一個(gè)點(diǎn)為參照求其他點(diǎn)連線的斜率，不需要計(jì)算斜率。
重點(diǎn)二：兩次循環(huán)體現(xiàn)重點(diǎn)一中的相對(duì)關(guān)系，可以讓j從i開始，節(jié)省時(shí)間。
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.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)...
摘要：哈希表復(fù)雜度時(shí)間空間思路一個(gè)點(diǎn)加一個(gè)斜率，就可以唯一的確定一條直線。這里，我們用哈希表，以斜率為，記錄有多少重復(fù)直線。注意哈希表的為，但是可以有正和負(fù)的，而且不一樣。 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ù)即可得到最簡分?jǐn)?shù)，一般求的是兩個(gè)正整數(shù)的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時(shí)為表示同一個(gè)點(diǎn)沒有意義，所以這道題我們規(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...
閱讀 1632·2021-11-25 09:43
閱讀 2528·2019-08-30 15:55
閱讀 1532·2019-08-30 13:08
閱讀 2777·2019-08-29 10:59
閱讀 897·2019-08-29 10:54
閱讀 1665·2019-08-26 18:26
閱讀 2674·2019-08-26 13:44
閱讀 2729·2019-08-23 18:36
