[Leetcode] Max Points on a Line 線上最大點數

ernest.wang 發布于2019-08-14 12:49 / 2715人閱讀

摘要：哈希表復雜度時間空間思路一個點加一個斜率，就可以唯一的確定一條直線。這里，我們用哈希表，以斜率為，記錄有多少重復直線。注意哈希表的為，但是可以有正和負的，而且不一樣。

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

哈希表 復雜度

時間 O(N^2) 空間 O(N)

思路

一個點加一個斜率，就可以唯一的確定一條直線。所以我們對每個點，都計算一下該點和其他點連線的斜率，這樣對于這個點來說，相同斜率的直線有多少條，就意味著有多少個點在同一條直線上，因為這些直線是相同的。另外，如果計算過點A和點B的直線，當算到點B時，就不用再和A連線了，因為AB這條直線上的點數已經都計算過了。這里，我們用哈希表，以斜率為key，記錄有多少重復直線。

注意

哈希表的Key為Double，但Double是可以有正0和負0的，而且不一樣。所以我們要用if(slope * slope == 0) slope = 0;把負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++){
            //過當前點的直線組成的哈希表，斜率為key
            HashMap lines = new HashMap();
            int vertical = 0, same = 1, currMax = 0;
            for(int j = i + 1; j < points.length; j++){
                // 統計相同的點
                if(points[i].x == points[j].x && points[i].y == points[j].y){
                    same++;
                    continue;
                }
                // 統計斜率為無窮的點，他們都在一條直線上
                if(points[i].x == points[j].x){
                    vertical++;
                    continue;
                }
                // 計算連線的斜率
                double slope = ((double)points[i].y - (double)points[j].y) / ((double)points[i].x - (double)points[j].x);
                // 修正負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)); 
            }
            // 經過該點的直線上最多的點數，我們在無窮斜率和正常斜率中選較大的，還要加上相同的點數
            currMax = Math.max(vertical, currMax) + same;
            max = Math.max(currMax, max);
        }
        return max;
    }
}

GPU云服務器云服務器 Points LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64724.html

[Leetcode] Max Points on a Line 直線上最多的點數

摘要：分子分母同時除以他們的最大公約數即可得到最簡分數，一般求的是兩個正整數的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時為表示同一個點沒有意義，所以這道題我們規定取值范圍。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the s...

張憲坤 2019-08-14 14:05 評論0 收藏0
[LintCode] Max Points on a Line

摘要：兩次循環對中第個和第個進行比較設置重復點數，相同斜率點數。內部循環每次結束后更新和點相同斜率的點的最大數目。外部循環每次更新為之前結果和本次循環所得的較大值。重點一以一個點為參照求其他點連線的斜率，不需要計算斜率。 Problem Given n points on a 2D plane, find the maximum number of points that lie on th...

bingo 2019-08-14 15:14 評論0 收藏0
leetcode-149-Max Points on a Line

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)...

darcrand 2019-07-31 11:03 評論0 收藏0
LeetCode 4

摘要：這個題的思路就是找數組里的兩個點，用這兩個點來做一條直線，然后看數組里的點都在直線上不，我用的是兩點式，需要考慮兩個點或坐標相同的特殊情況。 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...

zhkai 2019-08-14 11:46 評論0 收藏0
Leetcode 356. Line Reflection

摘要：題目解法這道題主要是判斷個點是否沿某條線對稱，可以從提示看出來所有的點應該要滿足所以先把所有的點掃一遍存下來，找到和然后再掃一遍，判定是否點都是延直線對稱的。時間復雜度空間復雜度代碼題目： Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the gi...

ivyzhang 2019-08-14 16:59 評論0 收藏0