判断点集中，最多有多少点在一条直线上。
我看AC率这么低，手很抖，但是别的题越来越难，又写不出来。
于是想了一个n^3的复杂度，能不过么？欧克，我想了想可以优化一下，每条直线我都弄成：
ax + by + c = 0
且a一定为正数。
优化的地方是：hash_map：abc是否已经计算过。是一个不是很好的优化。
但是结果出人意料，不优化16ms，优化284ms原因是用的map，map的查找是logn而不是1
anyway。也不是一次过的，提示下注意重复点的情况。
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;
}
};
|