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

2019-03-15  本文已影响0人  Haward_

给定一个二维平面,平面上有 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
上一篇下一篇

猜你喜欢

热点阅读