LeetCode 149 Max Points on a Line

LeetCode

Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

1 <= points.length <= 300 points[i].length == 2
-10<sup>4</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup> All the points are unique.

题目大意：

求在同一直线上的点的最大个数

解题思路：

固定一个点，求其与其他点的斜率是否相同，记录在map中。通过同一个点，若斜率相同，肯定在同一直线上。这是几何题。

解题步骤：

N/A

注意事项：

1. 两重循环，外循环为每个点，内循环为该点和其他的点的斜率。斜率可以为无穷大

Python代码：

def maxPoints(self, points: List[List[int]]) -> int:
	res = 0
	for i in range(len(points)):
		slope_to_count = collections.defaultdict(int)
		max_p = 0
		for j in range(i + 1, len(points)):
			slope = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]) \
				if points[j][0] - points[i][0] != 0 else float('inf') # remember line is y-axis
			slope_to_count[slope] += 1
			max_p = max(max_p, slope_to_count[slope])
		res = max(res, max_p + 1)
	return res

算法分析：

时间复杂度为O(n2)，空间复杂度O(n)