LeetCode 솔루션 분류
[1/8] 149. Max Points on a Line
본문
Given an array of points
where points[i] = [xi, yi]
represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Example 1:
Input: points = [[1,1],[2,2],[3,3]] Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4
Constraints:
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
- All the
points
are unique.
Accepted
319.6K
Submissions
1.3M
Acceptance Rate
24.6%
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
from collections import defaultdict
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
def calcdxdy(p1, p2):
if p1[0]-p2[0] == 0:
return p1[0]
slope = (p1[1]-p2[1])/(p1[0]-p2[0])
b = p1[1] - slope*p1[0]
return ( slope, b )
res = 0
for i in range(len(points)):
dic = defaultdict(int)
for j in range(i+1, len(points)):
dic[calcdxdy(points[i], points[j])] += 1
if dic: res = max( res, max(dic.values()) )
return res + 1