• Tweet

• Tweet

Max Points on Line leetcode

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

struct Point {
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};

//The STL includes the ordered and the unordered map (std::map and std::unordered_map) containers.
// In an ordered map the elements are sorted by the key, insert and access is in O(log n)).
// Usually the STL internally uses red black trees for ordered maps. But this is just an implementation detail.
// In an unordered map insert and access is in O(1). It is just another name for a hashtable.
int maxPoints(vector<Point> &points) {
unordered_map<double, int> map ;
int ret = 0;
int size = points.size();
for (int i = 0; i < size; i++) {
int invalidK = 0;
int add = 1;
for (int j = i + 1; j < size; j++) {
if (points[j].x == points[i].x) {
if (points[j].y == points[i].y) {
add++;
} else {
invalidK++;
}
continue;
}
double k = points[j].y == points[i].y ? 0.0
: (1.0 * (points[j].y – points[i].y))
/ (points[j].x – points[i].x);

if (map.find( k ) != map.end()) {
int count = map[k];
map[k]= count + 1;
} else {
map[k]= 1;
}
}
typedef unordered_map<double, int>::iterator map_iterator;
for(map_iterator i = map.begin(); i != map.end(); i++) {
if(i->second + add > ret)
{
ret= i->second + add;
}
}
ret = max(invalidK + add, ret);
map.clear();
}
return ret;
}