Max Points on Line leetcode

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;
}

3 thoughts on “Max Points on Line leetcode”

  1. I believe what you posted made a bunch of sense. However, think on this, what if you typed a
    catchier title? I am not suggesting your information is not solid, however
    what if you added a post title that grabbed folk’s attention? I mean find
    the maximum number of points that lie on the same straight line is kinda boring.
    You ought to glance at Yahoo’s home page and note how they create article titles to get viewers to click.
    You might add a related video or a related pic or two to get people interested about everything’ve got to say.

    In my opinion, it might make your blog a little bit more interesting.

Leave a Reply

Your email address will not be published. Required fields are marked *