Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6
my code: can't determine the hash value well.
this case can't pass.
[[0,0],[94911151,94911150],[94911152,94911151]]
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
int size = points.size();
int ans = 0;
if (size == 0) return 0;
unordered_map<double, int> mp;
double k;
for (int i = 0; i < size; ++i) {
int num = 0;
for (int j = i + 1; j < size; ++j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
num++;
continue;
}
if (points[j].x - points[i].x != 0)
k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x); // how to determine the hash value.
else k = INT_MAX;
mp[k]++;
}
if (mp[k] == 0) mp[k] = 1, num--;
for (auto it = mp.begin(); it != mp.end(); ++it) {
if (it->second > ans) {
ans = it->second;
ans += num;
}
}
mp.clear();
}
return ans+1;
}
};
In above test case, when it calculate the slope with [0,0] and [94911151,94911150] it comeback k = 1. So its not safe to store the hash k using the slope.
Now we have to change our strategy.
Approach #1: C++.
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
int size = points.size();
int ans = 0;
if (size == 0) return 0;
map<pair<int, int>, int> mp;
double k;
int dx, dy;
int flag;
for (int i = 0; i < size; ++i) {
int num = 0;
for (int j = i + 1; j < size; ++j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
num++;
continue;
}
dx = points[j].x - points[i].x;
dy = points[j].y - points[i].y;
flag = gcd(dx, dy);
mp[{dx/flag, dy/flag}]++;
}
ans = max(ans, num);
for (auto it = mp.begin(); it != mp.end(); ++it) {
if (it->second + num > ans) {
ans = it->second + num;
}
}
mp.clear();
}
return ans+1;
}
int gcd (int x, int y) {
if (y == 0) return x;
else return gcd(y, x%y);
}
};
In this case we use the pair of {dx, dy} as the hash key stroed in the map .
Approach #2: Java.
/**
* 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 maxPoints(Point[] points) {
if (points.length <= 0) return 0;
if (points.length <= 2) return points.length;
int result = 0;
for (int i = 0; i < points.length; ++i) {
HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
int samex = 1;
int samep = 0;
for (int j = 0; j < points.length; ++j) {
if (j != i) {
if (points[j].x == points[i].x && points[j].y == points[i].y) samep++;
if (points[j].x == points[i].x) {
samex++;
continue;
}
double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
if (hm.containsKey(k)) hm.put(k, hm.get(k)+1);
else hm.put(k, 2);
result = Math.max(result, hm.get(k)+samep);
}
}
result = Math.max(result, samex);
}
return result;
}
}
Approach #3: Python.
# Definition for a point.
# class Point(object):
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
class Solution(object):
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
l = len(points)
m = 0
for i in range(l):
dic = {'i' : 1}
same = 0
for j in range(i+1, l):
tx, ty = points[j].x, points[j].y
if tx == points[i].x and ty == points[i].y:
same += 1
continue
if points[i].x == tx: slope = 'i'
else: slope = (points[i].y - ty) * 1.0 / (points[i].x-tx)
if slope not in dic: dic[slope] = 1
dic[slope] += 1
m = max(m, max(dic.values()) + same)
return m
the python and the java versions have the same question with the first code, but I don't want to correct, because I'm not familiar with these language.XP