题目

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

方案一

  1. from fractions import Fraction
  3. class Solution:
  4.     def maxPoints(self, points: List[List[int]]) -> int:
  5.         '''ax+b=y
  6.         对于点(x1, y1),(x2, y2)
  7.         a = (y2 - y1) / (x2 - x1)
  8.         b = y1 - ax1
  9.         '''
  10.         if len(points) == 1:
  11.             return 1
  13.         res = 0
  14.         for i in range(len(points)):
  15.             duplicate = 1 # 重复点的个数
  16.             slope = {} # key: (y2 - y1) / (x2 - x1), value: int, 斜率相同的点的个数
  17.             for j in range(i + 1, len(points)):
  18.                 x1, y1 = points[i]
  19.                 x2, y2 = points[j]
  21.                 if x1 == x2 and y1 == y2: # 重复点的个数
  22.                     duplicate += 1
  23.                     continue
  24.                 if x1 - x2 == 0:  # 垂直线
  25.                     if float('inf') not in slope:
  26.                         slope[float('inf')] = 0
  27.                     slope[float('inf')] += 1
  28.                 elif y1 - y2 == 0:  # 水平线
  29.                     if 0 not in slope:
  30.                         slope[0] = 0
  31.                     slope[0] += 1
  32.                 else:
  33.                     slope_ = Fraction(y2 - y1, x2 - x1) # 防止精度问题，此处应又更好的解决方案
  34.                     if slope_ not in slope:
  35.                         slope[slope_] = 0
  36.                     slope[slope_] += 1
  37.             l = [v for v in slope.values()]
  38.             res = max(res, max(l) + duplicate) if l else max(res, duplicate)
  39.         return res
  • 双重遍历，在遍历的同时统计经过该点且斜率相同的点的个数，然后加上重复点的个数即是目标值

    注意水平线和垂直线的处理。

leetcode 解答（方案相同，效率却极好）

  1. class Solution:
  2.     def maxPoints(self, points: List[List[int]]) -> int:
  3.         cnt = collections.Counter((x, y) for x, y in points)
  4.         if len(cnt) <= 2:
  5.             return len(points)
  6.         ans = 0
  7.         for _ in range(1, len(cnt)):
  8.             (x1, y1), t1 = cnt.popitem()
  9.             slp =  collections.defaultdict(lambda: t1)
  10.             for (x2, y2), t2 in cnt.items():
  11.                 s = (y2 - y1) / (x2 - x1) if x1 != x2 else float('Inf')
  12.                 slp[s] += t2
  13.             ans = max(ans, max(slp.values()))
  14.         return ans
  • 怎么解决精度问题的？？？——没有解决精度问题，测试通过是因为cnt每次popitem的时候不会先弹出来(0, 0)这个点。具体请debug这个测试用例。

    points = [[0, 0], [94911151, 94911150], [94911152, 94911151]] 如果 popitem 第一次弹出 (0, 0) 则会出bug

原文

https://leetcode-cn.com/explore/orignial/card/all-about-lockup-table/239/learn-to-use-keys/1003/