BiruLyu
5/22/2017 - 7:49 PM

## 149. Max Points on a Line(# 1).java

``````# Time: O(n^2)
# Space: O(n)
# Max Points on a Line
'''
slope:
1. the same
2.1 inf
2.2 not inf

edge case:
python: [[0,0],[94911151,94911150],[94911152,94911151]]

Correct Code means you need to consider edge cases.

- point in points may be duplicate.
- use a*y + b*x + c = 0 to represent a line, not y = k*x + b, because k and b may be float number, and float numbers can't be compared with =. Two equal key in hash table representing line may differ.

'''
from collections import defaultdict
# Definition for a point.
class Solution(object):
def __init__(self, a=0, b=0):
self.x = a
self.y = b

def gcb(self, a, b):
while b:
a, b = b, a % b
return a

def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
from collections import defaultdict
result, lens, points = 0, len(points), map(lambda p: (p.x, p.y), points)
for i in range(lens):
x1, y1 = points[i]
same, lines = 1, defaultdict(int)
for j in range(i+1, lens):
x2, y2 = points[j]
if x1 == x2 and y1 == y2:
same += 1
else:
# [x1,y1],[x2,y2]
# [1,  6],[2, 4 ]
# y = kx + m
# a = k = (x1-x2)/(y1-y2); b = -1; c =
# c =
# ax + by + c = 0
# a = -4 + 6, b = -1 + 2, c = -6*2 + 4*1

if y2 < y1 or y2 == y2 and x1 < x2:
a, b, c = - y2 + y1, - x1 + x2, - y1 * x2 + y2 * x1
else:
a, b, c = y2 - y1, x1 - x2, y1 * x2 - y2 * x1
rate = self.gcb(self.gcb(a, b), c)
lines[(a / rate, b / rate, c /rate)] += 1
result = max(result, (max(lines.values()) if lines.values() else 0) + same)
return result

# class Solution(object):
#     def maxPoints(self, points):
#         """
#         :type points: List[Point]
#         :rtype: int
#         """
#         max_points = 0
#         for i, start in enumerate(points):
#             slope_count, same = collections.defaultdict(int), 1
#             for j in xrange(i + 1, len(points)):
#                 end = points[j]
#                 # the same points
#                 if start.x == end.x and start.y == end.y:
#                     same += 1
#                 else:

#                     # slope is inf
#                     slope = float("inf")
#                     if start.x - end.x != 0:
#                         # slope is not inf
#                         slope = (start.y - end.y) * 1.0 / (start.x - end.x)
#                     slope_count[slope] += 1

#             current_max = same
#             for slope in slope_count:
#                 current_max = max(current_max, slope_count[slope] + same)

#             max_points = max(max_points, current_max)

#         return max_points``````
``````/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if(points == null || points.length == 0) return 0;
if(points.length <= 2) return points.length;
int res = 0;
//HashMap<Double, Integer> map = new HashMap<Double, Integer>();
for(int i = 0; i < points.length; i++){
HashMap<String, Integer> map = new HashMap<String, Integer>();// each points:storing the different k and frequency
int sameX = 1;
int sameP = 0;
for(int j = 0; j < points.length; j++){
if(i != j){
if(points[i].x == points[j].x && points[i].y == points[j].y ){
sameP++;
}
if(points[i].x == points[j].x){
sameX++;
continue;// deal with a zero denominator
}
//double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
//In order to avoid using double type(the slope k) as map key, I used pair (int a, int b) as the key where a=pj.x-pi.x, b=pj.y-pi.y, and k=b/a. Using greatest common divider of a and b to divide both a, b ensures that lines with same slope have the same key.
//eg:[[0,0],[94911151,94911150],[94911152,94911151]]

int a = points[j].y - points[i].y;
int b = points[j].x - points[i].x;
int gcd = gcd(a,b);

String hashStr = (a/gcd) + "_" + (b/gcd);
if(map.containsKey(hashStr)){
map.put(hashStr, map.get(hashStr) + 1);
} else {
map.put(hashStr, 2);
}
res = Math.max(res, map.get(hashStr) + sameP);
}
}
res = Math.max(res, sameX);
}
return res;
}

public int gcd(int x, int y){
return (y == 0) ? x : gcd(y, x % y);
//辗转相除法
/*
60 : 12 12 12 12 12
24 : 12 12
60 % 24 = 12 找到了最小的一块
24 % 12 = 0  找完了！

*/
}

}``````
``````/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
class Solution {
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public int maxPoints(Point[] points) {
if (points == null || points.length < 1) return 0;
int len = points.length;
if (len <= 2) return len;
int res = 2;
for (int i = 0; i < len; i++) {
if (res >= len - i) return res; // if the number of the left points is less than res
Map<String, Integer> map = new HashMap<>();
int sameX = 1;
int sameP = 0;
int diff = 0;
for (int j = i + 1; j < len; j++) {
if (i != j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
sameP++;
}
if (points[i].x == points[j].x) {
sameX++;
continue;
}

int a = points[i].x - points[j].x;
int b = points[i].y - points[j].y;
int gcd = gcd(a,b);
String hashStr = (b / gcd) + "_" + (a / gcd);
map.put(hashStr, map.getOrDefault(hashStr, 1) + 1);
diff = Math.max(diff, map.get(hashStr));
}
}
res = Math.max(res,Math.max(diff + sameP, sameX));
}
return res;
}
}``````