Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一堆二维点,问最多多少个点共线
O(n2)枚举两个点,看一样斜率的最多多少个点,2014年曾经用C++写过👉http://www.cppblog.com/Uriel/articles/205287.html
今日在Discussion看到个不错的思路(👉https://leetcode.com/problems/max-points-on-a-line/solutions/3016632/python-3-11-lines-w-explanation-and-example-t-m-95-97/),不需要折腾double型求斜率,因为点的坐标都是int型,可以求两个点dx,dy,除以GCD之后用dict统计这样的约简后的数对有多少个,因为存的是除以GCD之后的数对,所以一开始要给所有点按x值从小到大排序,保证单调增

 1 #149
 2 #Runtime: 77 ms (Beats 92.29%)
 3 #Memory: 13.8 MB (Beats 94.26%)
 4 
 5 class Solution:
 6     def maxPoints(self, points: List[List[int]]) -> int:
 7         points.sort()
 8         ans = 0
 9         for i, (x1, y1) in enumerate(points):
10             k = defaultdict(int)
11             for x2, y2 in points[i + 1 :]:
12                 dx = x2 - x1
13                 dy = y2 - y1
14                 g = gcd(dx, dy)
15                 kk = (dx // g, dy // g)
16                 k[kk] += 1
17                 ans = max(ans, k[kk])
18         return ans + 1

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理