[LeetCode]149 直线上最多的点数

题目描述

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

示例1

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
    ^
    |
    |        o
    |     o
    |  o  
    +------------->
    0  1  2  3  4

示例2

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
    ^
    |
    |  o
    |     o        o
    |        o
    |  o        o
    +------------------->
    0  1  2  3  4  5  6

思路

  • 任意不同的两点确定一条直线,遍历所有点是否在该线上,并计数
  • Points中有重复的点,所以首先得利用map去重并分别记录点的个数,可以大大减少多层for循环中判断三点是否同一直线的次数,
  • 不同点不超过2个,则所有点在同一条线上

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        if points == None :
            return 0
        m = len(points)
        if m <= 2:
            return m
        maxline = 0
        for i in range(m):
            dup =  1
            d = {}
            d['inf'] = 0
            for j in range((i+1),m):
                if points[i].x == points[j].x and points[j].y == points[i].y:
                    dup +=1
                elif points[j].x == points[i].x:
                    d['inf'] += 1
                else:
                    k = 1.0*(points[j].y - points[i].y)/(points[j].x - points[i].x)
                    if k in d:
                        d[k] += 1
                    else:
                        d[k] = 1 
            maxline = max( max(d.values()) + dup,maxline)
            
        return maxline