美文网首页
最多有多少个点在同一条直线上

最多有多少个点在同一条直线上

作者: Haward_ | 来源:发表于2019-03-15 21:04 被阅读0次

    给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
    https://leetcode-cn.com/problems/max-points-on-a-line/

    class Point:
        def __init__(self, a=0, b=0):
            self.x = a
            self.y = b
    
    class Solution:
        def maxPoints(self, points):
            size = len(points)
            if size in [0,1]:
                return size
            res = 0
            for i in range(size):
                cur_max = 1
                d = {}
                count = 0
                dup = 0
                for j in range(size):
                    if j!=i:
                        deta_x = points[i].x - points[j].x
                        deta_y = points[i].y - points[j].y
                        if deta_x == 0 and deta_y == 0:
                            dup += 1
                        elif deta_x == 0:
                            if count == 0:
                                count = 2
                            else:
                                count += 1
                            cur_max = max(count,cur_max)
                        else:
                            k = deta_y/deta_x
                            if d.get(k) == None:
                                d[k] = 2
                            else:
                                d[k] += 1
                            cur_max = max(d[k],cur_max)
                res = max(res,cur_max + dup)
            return res
    

    相关文章

      网友评论

          本文标题:最多有多少个点在同一条直线上

          本文链接:https://www.haomeiwen.com/subject/igfepqtx.html