首页 > 代码库 > LeetCode "Max Points on a Line "
LeetCode "Max Points on a Line "
The first solution I figured out is O(n^3). I thought it must be O(n^2) to get max points on a line for a given point.. but after checking several articles, I found it surprisingly easy: it is just like counting sort, so O(n) is possible :)
class Solution {public: float trunc(float f) { const int Scale = 10000000; int x = f * Scale; return x * 1.0 / Scale; } bool isSame(Point &a, Point &b) { return a.x == b.x && a.y == b.y; } int maxPoints(vector<Point> &points) { if(points.size() == 0) return 0; if(points.size() == 1) return 1; int ret = 0; int cnt = points.size(); for(int i = 0; i < cnt; i ++) { int nDup = 0, currMax = 1; unordered_map<float, vector<Point>> smap; Point &r = points[i]; for(int j = 0; j < cnt; j ++) { if (j == i) continue; // self? Point &r1 = points[j]; if(isSame(r, r1)) // overlapped? { nDup ++; continue; } // Get Slope hash int dy = r1.y - r.y; int dx = r1.x - r.x; float key = 0; if(abs(dx) > 0) key = trunc(dy * 1.0 / dx); else key = std::numeric_limits<float>::max(); // Update record if(smap.find(key) == smap.end()) { vector<Point> init; init.push_back(r); init.push_back(r1); smap.insert(make_pair(key, init)); } else { smap[key].push_back(r1); } // Get max so far currMax = currMax < smap[key].size() ? smap[key].size() : currMax; } currMax += nDup; ret = currMax > ret ? currMax : ret; } return ret; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。