149. Max Points on a Line
计算一个列表中最多能有几个点在一条线上。
思路是两个for循环，需要比较(n - 1) + .. + 2 + 1 = (n - 1) * n/2次，用字典记录下各个斜率（或者点）出现的次数。最后返回结果为一次迭代中最多的点+重复的点+本身
Python
如果使用这种方法的话需要在slope = Decimal(dy * 1.0) / dx if dx != 0 else 'infinity'dy前面加上decimal，因为浮点数精度可能出现问题导致不同的点算出相同的斜率。
def maxPoints2(self, points):
"""
:type points: List[Point]
:rtype: int
"""
if len(points) <= 2: return len(points)
result = 0
d = defaultdict(int)
for i in range(0, len(points)):
d.clear()
overlap, cur_max = 0, 0
for j in range(i + 1, len(points)):
dx, dy = points[j].x - points[i].x, \
points[j].y - points[i].y
if dx == 0 and dy == 0:
overlap += 1
continue
slope = Decimal(dy * 1.0) / dx if dx != 0 else 'infinity'
d[slope] += 1
cur_max = max(cur_max, d[slope])
result = max(result, cur_max + overlap + 1)
return result
第二种方法使用求x, y的GCD来同时缩小x，y的范围避免浮点数的精度问题。
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
if len(points) <= 2: return len(points)
d = defaultdict(int)
result = 0
for i in range(0, len(points)):
d.clear() # clear dict for each round
cur_max, overlap = 0, 0
for j in range(i + 1, len(points)):
dx, dy = points[j].x - points[i].x, \
points[j].y - points[i].y
if dx == 0 and dy == 0:
overlap += 1
continue
gcd = self.getGCD(dx, dy) # get the common greatest divisor
print("gcd", gcd)
dx //= gcd
dy //= gcd # decrease the x and y at the same time to prevent overflow
d[(dx, dy)] += 1
cur_max = max(cur_max, d[(dx, dy)])
result = max(result, cur_max + overlap + 1)
return result
def getGCD(self, i, j):
if j == 0: return i
return self.getGCD(j, i % j)
运行例子
input = [[0, 0], [1, 0], [1, 1], [2, 2]]
^
2| o
1| o
o--o---------------->
0 1 2 3 4 5 6
# first iteration
{(1, 0): 1})
{(1, 0): 1, (1, 1): 1})
{(1, 0): 1, (1, 1): 2}) # (1，1)中有两个点斜率相等 返回最大值3
# second iteration
{(0, 1): 1})
{(0, 1): 1, (1, 2): 1})
# third iteration
{(1, 1): 1})
Java
使用Java重写python第二种方法的时候，逻辑上只要xy相等point就算相等，需要重写Point中的equals和hashCode方法，hashcode方法在每次存储或者查找map的时候计算Point存放的位置，equals用来比较两个点的x,y是否相等。
还有一种比较快的方法没有看，好像是直接比较乘法。
class Point {
int x;
int y;
Point(int a, int b) {
x = a;
y = b;
}
@Override
public boolean equals(Object other) {
if (other == this) return true;
if (!(other instanceof Point)) return false;
Point o = (Point) other;
return this.x == o.x && this.y == o.y;
}
public int hashCode() {
return x * 4 + y * 3;
}
}
class Solution {
public int maxPoints(Point[] points) {
int result = 0;
int size = points.length;
Map<Point, Integer> map = new HashMap<>();
for (int i = 0; i < size; i++) {
int curmax = 0,
overlap = 0;
map.clear();
for (int j = i + 1; j < size; j++) {
int dx = points[j].x - points[i].x,
dy = points[j].y - points[i].y;
if (dx == 0 && dy == 0) {
overlap++;
continue;
}
int gcd = getGCD(dx, dy);
dx /= gcd;
dy /= gcd;
Point t = new Point(dx, dy);
if (map.containsKey(t)) {
int count = map.get(t) + 1;
map.put(t, count);
} else {
map.put(t, 1);
}
curmax = Math.max(curmax, map.get(t));
}
result = Math.max(result, curmax + overlap + 1);
}
return result;
}
Ref
https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes
https://leetcode.com/problems/max-points-on-a-line/discuss/47268/Two-concise-python-solutions