Determine the maximum number of points from a set that lie on the same line.
Seeing the low acceptance rate made me nervous, but the other problems were getting harder and I could not solve them.
So I came up with an O(n^3) approach – could it pass? I thought about optimizing: represent each line as:
ax + by + c = 0
where a is always positive.
The optimization was to use a hash_map to check whether a given (a, b, c) has already been computed. It is not a great optimization.
But the result was surprising: without optimization it ran in 16ms, with optimization 284ms. The reason is that I used map, whose lookup is O(log n) instead of O(1).
Anyway, it did not pass on the first try either – note the edge case of duplicate points.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public:
int maxPoints(vector<Point> &points) {
vector<Point> pointstmp;
pointstmp.clear();
int counts[1000];
for(int i = 0; i < points.size(); i++) {
int tmp = 0;
int j;
for(j = 0; j < pointstmp.size(); j++) {
if(pointstmp[j].x == points[i].x && pointstmp[j].y == points[i].y) {
break;
}
}
if(j < pointstmp.size()) {
counts[j]++;
} else {
pointstmp.push_back(points[i]);
counts[pointstmp.size()-1] = 1;
}
}
if(pointstmp.size() == 0) return 0;
if(pointstmp.size() == 1) return counts[0];
if(pointstmp.size() == 2) return counts[0] + counts[1];
int ans = 2;
map<vector<int>, bool> mapv;
mapv.clear();
for(int i = 0; i < pointstmp.size()-2; i++) {
for(int j = i+1; j < pointstmp.size()-1; j++) {
int x1 = pointstmp[i].x;
int y1 = pointstmp[i].y;
int x2 = pointstmp[j].x;
int y2 = pointstmp[j].y;
if(x1 == x2 && y1 == y2) continue;
int a = y1 - y2;
int b = -(x1 - x2);
int c = (x1 - x2) * y1 - (y1 - y2) * x1;
// if(a < 0) {
// a = a * (-1);
// b = b * (-1);
// c = c * (-1);
// }
// vector<int> tmp;
// tmp.clear();
// tmp.push_back(a);
// tmp.push_back(b);
// tmp.push_back(c);
// if(mapv.find(tmp) != mapv.end()) continue;
// mapv.insert(map<vector<int>, bool>::value_type(tmp, true));
int count = counts[i] + counts[j];
for(int k = j+1; k < pointstmp.size(); k++) {
int x = pointstmp[k].x;
int y = pointstmp[k].y;
if(isInLine(a, b, c, x, y)) count += counts[k];
}
if(count > ans) ans = count;
}
}
return ans;
}
private:
bool isInLine(int a, int b, int c, int x, int y) {
return a * x + b * y + c == 0;
}
};
|