推 SecondRun: 還以為你說nlogn是這題 我誤會了 01/08 23:32
→ pandix: 阿 原來是這樣 沒想到今天每日剛好是hard 01/08 23:33
推 AyuniD: 靠原來這麼簡單哦 01/09 02:26
→ Rushia: :( 01/09 09:01
推 NTHUlagka: 大師 01/09 09:44
149. Max Points on a Line
平面上有很多點，問你最多能讓幾點共線
Example 1:
https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
思路:
1.對每個點都去算其他點和他的斜率 一樣的話就是在同一條線上
斜率可以拿來當成 dict 的 key 最後檢查哪個 key 的 value 最高就好
自己和自己的斜率最後再扣掉
樸實的O(n^2)
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
res = 0
for p1 in points:
slope = defaultdict(int)
for p2 in points:
if p1[0] - p2[0] != 0:
slope[(p1[1] - p2[1]) / (p1[0] - p2[0])] += 1
else:
slope[inf] += 1
slope[inf] -= 1
res = max(res, max(slope.values()))
return res+1
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.200.200 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673191323.A.8B3.html