資訊專欄INFORMATION COLUMN
摘要：哈希表復(fù)雜度時(shí)間空間思路一個(gè)點(diǎn)加一個(gè)斜率，就可以唯一的確定一條直線。這里，我們用哈希表，以斜率為，記錄有多少重復(fù)直線。注意哈希表的為，但是可以有正和負(fù)的，而且不一樣。
Max Points on a Line
哈希表 復(fù)雜度Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
時(shí)間 O(N^2) 空間 O(N)
思路一個(gè)點(diǎn)加一個(gè)斜率，就可以唯一的確定一條直線。所以我們對(duì)每個(gè)點(diǎn)，都計(jì)算一下該點(diǎn)和其他點(diǎn)連線的斜率，這樣對(duì)于這個(gè)點(diǎn)來(lái)說(shuō)，相同斜率的直線有多少條，就意味著有多少個(gè)點(diǎn)在同一條直線上，因?yàn)檫@些直線是相同的。另外，如果計(jì)算過(guò)點(diǎn)A和點(diǎn)B的直線，當(dāng)算到點(diǎn)B時(shí)，就不用再和A連線了，因?yàn)锳B這條直線上的點(diǎn)數(shù)已經(jīng)都計(jì)算過(guò)了。這里，我們用哈希表，以斜率為key，記錄有多少重復(fù)直線。
注意哈希表的Key為Double，但Double是可以有正0和負(fù)0的，而且不一樣。所以我們要用if(slope * slope == 0) slope = 0;把負(fù)0都變成正0
代碼public class Solution {
public int maxPoints(Point[] points) {
if(points.length <= 1) return points.length;
int max = Integer.MIN_VALUE;
for(int i = 0; i < points.length; i++){
//過(guò)當(dāng)前點(diǎn)的直線組成的哈希表，斜率為key
HashMap lines = new HashMap();
int vertical = 0, same = 1, currMax = 0;
for(int j = i + 1; j < points.length; j++){
// 統(tǒng)計(jì)相同的點(diǎn)
if(points[i].x == points[j].x && points[i].y == points[j].y){
same++;
continue;
}
// 統(tǒng)計(jì)斜率為無(wú)窮的點(diǎn)，他們都在一條直線上
if(points[i].x == points[j].x){
vertical++;
continue;
}
// 計(jì)算連線的斜率
double slope = ((double)points[i].y - (double)points[j].y) / ((double)points[i].x - (double)points[j].x);
// 修正負(fù)0
if(slope * slope == 0) slope = 0;
lines.put(slope, lines.containsKey(slope) ? lines.get(slope) + 1 : 1);
currMax = Math.max(currMax, lines.get(slope));
}
// 經(jīng)過(guò)該點(diǎn)的直線上最多的點(diǎn)數(shù)，我們?cè)跓o(wú)窮斜率和正常斜率中選較大的，還要加上相同的點(diǎn)數(shù)
currMax = Math.max(vertical, currMax) + same;
max = Math.max(currMax, max);
}
return max;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64724.html
摘要：分子分母同時(shí)除以他們的最大公約數(shù)即可得到最簡(jiǎn)分?jǐn)?shù)，一般求的是兩個(gè)正整數(shù)的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時(shí)為表示同一個(gè)點(diǎn)沒(méi)有意義，所以這道題我們規(guī)定取值范圍。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the s...
摘要：兩次循環(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 th...
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)...
摘要：這個(gè)題的思路就是找數(shù)組里的兩個(gè)點(diǎn)，用這兩個(gè)點(diǎn)來(lái)做一條直線，然后看數(shù)組里的點(diǎn)都在直線上不，我用的是兩點(diǎn)式，需要考慮兩個(gè)點(diǎn)或坐標(biāo)相同的特殊情況。 Max Points on a Line https://oj.leetcode.com/problems/max-points-on-a-line/ Given n points on a 2D plane, find the maximu...
摘要：題目解法這道題主要是判斷個(gè)點(diǎn)是否沿某條線對(duì)稱，可以從提示看出來(lái)所有的點(diǎn)應(yīng)該要滿足所以先把所有的點(diǎn)掃一遍存下來(lái)，找到和然后再掃一遍，判定是否點(diǎn)都是延直線對(duì)稱的。時(shí)間復(fù)雜度空間復(fù)雜度代碼 題目： Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the gi...
閱讀 836·2025-02-07 13:29
閱讀 644·2024-11-07 18:25
閱讀 131094·2024-02-01 10:43
閱讀 1060·2024-01-31 14:58
閱讀 1022·2024-01-31 14:54
閱讀 83215·2024-01-29 17:11
閱讀 3497·2024-01-25 14:55
閱讀 2217·2023-06-02 13:36
