leeyupeng

leeyupeng@126.com

0%

leetcode.149.直线上最多的点数

发表于 更新于 分类于 ， 阅读次数： Valine：

直线上最多的点数

问题描述

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

暴力法

思路分析

三个点 (x1,y1),(x2,y2),(x3,y3)是否在一条直线上的判定条件是:
$\frac{(y2-y1)}{(x2-x1)}$ = $\frac{(y3-y1)}{(x3-x1)}$

特殊考虑到 x2 == x1, y2 == y1的情况

完美解决
执行用时 :88 ms, 在所有 C++ 提交中击败了14.36%的用户
内存消耗 :7.5 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

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
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		if (points.size() <= 2)
		{
			return points.size();
		}
		int ans = 0;
		int n = points.size();
		vector<int> startPoint;
		vector<int> endPoint;
		int count;
		long long offsetx;
		long long offsety;
		long long offsetkx;
		long long offsetky;

		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				offsetx = points[j][0] - points[i][0];
				offsety = points[j][1] - points[i][1];

				count = 0;
				for (int k = 0; k < n; k++)
				{
					offsetkx = points[k][0] - points[i][0];
					offsetky = points[k][1] - points[i][1];
					if (offsetx == 0 && offsety == 0) {
						if (offsetkx == 0 && offsetky == 0) { count++; }
						continue;
					}
					if (offsetx * offsetky == offsetkx * offsety) { count++; }
				}
				ans = max(ans, count);
			}
		}
		return ans;
	}
};

暴力算法

思路分析

去除重叠点
两点确定一条线，然后计算出所有的在这条直线上的点，更新ans

完美解决
执行用时 :24 ms, 在所有 C++ 提交中击败了70.50%的用户
内存消耗 :7.4 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

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
66
67
68
69
70
71
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		vector<int> nums(points.size(),0);

		{
			int i = 0;
			while (i < points.size())
			{
				nums[i] = 1;
				for (int j = points.size() - 1; j > i; j--)
				{
					if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
						points.erase(points.begin() + j);
						nums[i]++;
					}
				}
				i++;
			}
		}

		if (points.size() == 1)
		{
			return nums[0];
		}
		else if (points.size() == 2)
		{
			return nums[0] + nums[1];
		}

		int n = points.size();
		vector<vector<bool>> matrix(n);
		for (int i = 0; i < n; i++)
		{
			matrix[i].insert(matrix[i].begin(), points.size(), false);
		}

		int ans = 0;
		vector<int> startPoint;
		vector<int> endPoint;
		int count;
		long long offsetx;
		long long offsety;
		long long offsetkx;
		long long offsetky;

		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				if (matrix[i][j]) { continue; }
				offsetx = points[j][0] - points[i][0];
				offsety = points[j][1] - points[i][1];

				count = nums[i] + nums[j];
				for (int k = j+1; k < n; k++)
				{
					if (matrix[i][k]) { break; }
					if (matrix[j][k]) { break; }
					offsetkx = points[k][0] - points[i][0];
					offsetky = points[k][1] - points[i][1];
					if (offsetx * offsetky == offsetkx * offsety) {
						count += nums[k]; matrix[i][k] = true; matrix[j][k] = true;
					}
				}
				ans = max(ans, count);
			}
		}
		return ans;
	}
};

代码实现

1.matrix[i][j] 和i,j在一条直线上的点计算过 不再重复计算
2.i右侧的点总和也不大于ans时break;
3.matrix[i][j] i,j,已经计算过，说明后面的计算不会出现 i，j在同一条直线上，rightnums可以减去两者中的小值

执行用时 :8 ms, 在所有 C++ 提交中击败了99.73%的用户
内存消耗 :7.6 MB, 在所有 C++ 提交中击败了100.00%的用户 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Solution {
	public:
		int maxPoints(vector<vector<int>>& points) {
			vector<int> nums(points.size(), 0);

			{
				int i = 0;
				while (i < points.size())
				{
					nums[i] = 1;
					for (int j = points.size() - 1; j > i; j--)
					{
						if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
							points.erase(points.begin() + j);
							nums[i]++;
						}
					}
					i++;
				}
			}

			if (points.size() == 1)
			{
				return nums[0];
			}
			else if (points.size() == 2)
			{
				return nums[0] + nums[1];
			}

			int n = points.size();

			int temp;
			for (int i = 0; i < n; i++)
			{
				for (int j = i + 1; j < n; j++)
				{
					if (nums[i] < nums[j])
					{
						temp = nums[i];
						nums[i] = nums[j];
						nums[j] = temp;

						temp = points[i][0];
						points[i][0] = points[j][0];
						points[j][0] = temp;

						temp = points[i][1];
						points[i][1] = points[j][1];
						points[j][1] = temp;
					}
				}
			}

			int maxnums = 0;

			for (int i = 0; i < n; i++)
			{
				maxnums += nums[i];
			}

			vector<vector<bool>> matrix(n);
			for (int i = 0; i < n; i++)
			{
				matrix[i].insert(matrix[i].begin(), points.size(), false);
			}

			int ans = 0;

			int count;
			long long offsetx;
			long long offsety;
			long long offsetkx;
			long long offsetky;

			int rightnums = maxnums;

			for (int i = 0; i < n; i++)
			{
				for (int j = i + 1; j < n; j++)
				{
					if (matrix[i][j]) { continue; }
					offsetx = points[j][0] - points[i][0];
					offsety = points[j][1] - points[i][1];

					count = nums[i] + nums[j];
					for (int k = j + 1; k < n; k++)
					{
						if (matrix[i][k]) { break; }
						if (matrix[j][k]) { break; }
						offsetkx = points[k][0] - points[i][0];
						offsetky = points[k][1] - points[i][1];
						if (offsetx * offsetky == offsetkx * offsety) {
							count += nums[k]; matrix[i][k] = true; matrix[j][k] = true;
							rightnums -= min(nums[j], nums[k]);
						}
					}
					ans = max(ans, count);
				}

				rightnums -= nums[i];
				if (ans >= rightnums) { break; }
			}
			return ans;
		}
};

动态规划

思路分析

dp[i][j] 代表以i，j为起始点的线段，和i，j在同一个直线上的点的最大数量
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]-1)
要求 i k j 在一条直线上

需要考虑到i,k,j共点的情况

代码实现

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
66
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		if (points.size() <= 2)
		{
			return points.size();
		}
		int n = points.size();
		long long offsetx;
		long long offsety;
		long long offsetikx;
		long long offsetiky;
		long long offsetkjx;
		long long offsetkjy;
		vector<vector<int>> dp(n);
		for (int i = 0; i < n; i++)
		{
			dp[i].insert(dp[i].begin(), n, 0);
			dp[i][i] = 1;
		}
		int i, j, dis;
		int k;
		for (dis = 1; dis < n; dis++)
		{
			for (i = 0; i < n - dis; i++)
			{
				j = i + dis;
				offsetx = points[j][0] - points[i][0];
				offsety = points[j][1] - points[i][1];
				dp[i][j] = 2;
				for (k = i + 1; k < j; k++)
				{
					offsetikx = points[k][0] - points[i][0];
					offsetiky = points[k][1] - points[i][1];
					offsetkjx = points[j][0] - points[k][0];
					offsetkjy = points[j][1] - points[k][1];
					if (offsetx == 0 && offsety == 0) {
						if (offsetikx == 0 && offsetiky == 0) {
							if (i + 1 == k && k + 1 == j) {}
							else { continue; }
						}
					}
					else if (offsetikx == 0 && offsetiky == 0 && i + 1 != k) {
						dp[i][j] = max(dp[i][j], 1 + dp[k][j]); continue;
					}
					else if (offsetkjx == 0 && offsetkjy == 0 && k + 1 != j) {
						dp[i][j] = max(dp[i][j], dp[i][k] + 1); continue;
					}

					if (offsetx * offsetiky == offsetikx * offsety) {
						dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] - 1);
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				ans = max(ans, dp[i][j]);
			}
		}
		return ans;
	}
};

动态规划

思路分析

dp[i][j] 代表以i，j为起始点的线段，和i，j在同一个直线上的点的最大数量
转移方程
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]-1)
要求 i k j 在一条直线上

需要考虑到i,k,j共点的情况
去除相同点

完美解决
执行用时 :16 ms, 在所有 C++ 提交中击败了89.02%的用户
内存消耗 :7.9 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

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
66
67
68
69
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		if (points.size() <= 2)
		{
			return points.size();
		}
		vector<vector<int>> dp(points.size());
		for (int i = 0; i < points.size(); i++)
		{
			dp[i].insert(dp[i].begin(), points.size(), 0);
			dp[i][i] = 1;
		}
		{
			int i = 0;
			while (i < points.size())
			{
				for (int j = points.size() - 1; j > i; j--)
				{
					if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
						points.erase(points.begin() + j);
						dp[i][i]++;
					}
				}
				i++;
			}
		}
		int n = points.size();
		if (n == 1)
		{
			return dp[0][0];
		}
		long long offsetx;
		long long offsety;
		long long offsetikx;
		long long offsetiky;

		int i, j, dis;
		int k;
		for (dis = 1; dis < n; dis++)
		{
			for (i = 0; i < n - dis; i++)
			{
				j = i + dis;
				offsetx = points[j][0] - points[i][0];
				offsety = points[j][1] - points[i][1];
				dp[i][j] = dp[i][i] + dp[j][j];
				for (k = i + 1; k < j; k++)
				{
					offsetikx = points[k][0] - points[i][0];
					offsetiky = points[k][1] - points[i][1];

					if (offsetx * offsetiky == offsetikx * offsety) {
						dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] - dp[k][k]);
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				ans = max(ans, dp[i][j]);
			}
		}
		return ans;
	}
};

RANSAC算法

思路分析

每次从数组中抽取两点组成一点直线，计算在这条直线上点，更新ans

RANSAC能得出一个仅仅用局内点计算出模型，并且概率还足够高。但是，RANSAC并不能保证结果一定正确，为了保证算法有足够高的合理概率，我们必须小心的选择算法的参数。

迭代次数：

1
2
3
double p = 0.9;
double p_inliers = double(ans) / double(maxnums);
int N = ceil(log(1 - p) / log(1 - pow(p_inliers, 2)));

有小概率 WA

执行用时 :4 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.3 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		if (points.size() <= 2)
		{
			return points.size();
		}
		vector<int> nums(points.size(), 0);

		{
			int i = 0;
			while (i < points.size())
			{
				nums[i] = 1;
				for (int j = points.size() - 1; j > i; j--)
				{
					if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
						points.erase(points.begin() + j);
						nums[i]++;
					}
				}
				i++;
			}
		}

		if (points.size() == 1)
		{
			return nums[0];
		}
		else if (points.size() == 2)
		{
			return nums[0] + nums[1];
		}

		int n = points.size();

		int maxnums = 0;

		for (int i = 0; i < n; i++)
		{
			maxnums += nums[i];
		}

		vector<vector<bool>> matrix(n);
		for (int i = 0; i < n; i++)
		{
			matrix[i].insert(matrix[i].begin(), points.size(), false);
			matrix[i][i] = true;
		}

		int ans = 2;

		int count;
		long long offsetx;
		long long offsety;
		long long offsetkx;
		long long offsetky;

		double p = 0.9;
		double p_inliers = double(ans) / double(maxnums);
		int N = ceil(log(1 - p) / log(1 - pow(p_inliers, 2)));
		int kk = 0;

		int temp;
		int i, j, k;
		srand((unsigned)time(NULL));
		while (kk++ < N)
		{

			i = rand() % n;
			j = rand() % n;

			if (matrix[i][j] == true || matrix[j][i] == true) { continue; }

			offsetx = points[j][0] - points[i][0];
			offsety = points[j][1] - points[i][1];

			count = 0;
			for (int k = 0; k < n; k++)
			{
				offsetkx = points[k][0] - points[i][0];
				offsetky = points[k][1] - points[i][1];
				if (offsetx * offsetky == offsetkx * offsety) {
					count += nums[k];
					matrix[i][k] = true; matrix[j][k] = true;
					matrix[k][i] = true; matrix[k][j] = true;
				}
			}
			if (count > ans)
			{
				ans = count;

				p_inliers = double(ans) / double(maxnums);
				N = ceil(log(1 - p) / log(1 - pow(p_inliers, 2)));
			}
		}
		return ans;
	}
};

空间压缩

思路分析

根据每个点的x，排序
根据每个点的y，排序

思路错误
超时

代码实现

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) {
		int ans = 0;
		vector<int> matrixx;
		vector<int> matrixy;
		map<int,int> xmap;
		map<int,int> ymap;
		for (int i = 0; i < points.size(); i++)
		{
			if (xmap.find(points[i][0]) == xmap.end()) { xmap.insert({ points[i][0],0 }); matrixx.push_back(points[i][0]); }
			if (ymap.find(points[i][1]) == ymap.end()) { ymap.insert({ points[i][1],0 }); matrixy.push_back(points[i][1]); }
		}
		sort(matrixx.begin(), matrixx.end());
		sort(matrixy.begin(), matrixy.end());
		for (int i = 0; i < matrixx.size(); i++)
		{
			xmap[matrixx[i]] = i;
		}
		for (int i = 0; i < matrixy.size(); i++)
		{
			ymap[matrixy[i]] = i;
		}
		vector<vector<int>> matrix(xmap.size());
		for (int i = 0; i < xmap.size(); i++)
		{
			matrix[i].insert(matrix[i].begin(), ymap.size(), 0);
		}
		long long x, y;
		int indexx, indexy;
		for (int i = 0; i < points.size(); i++)
		{
			x = points[i][0];
			y = points[i][1];
			indexx = xmap[x];
			indexy = ymap[y];
			matrix[indexx][indexy] ++;
		}

		int n = matrixx.size();
		int m = matrixy.size();

		int count = 0;
		long long offsetx;
		long long offsety;
		long long temp;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{				
				if (matrix[i][j] == 0)
				{
					continue;
				}
				for (int ii = 0; ii < n-i; ii++)
				{
					offsetx = matrixx[i + ii] - matrixx[i];
					//if (offsetx != 0  && ans > (matrixx[n - 1] - matrixx[i] + 1) / offsetx){break; }
					for (int jj = -j; jj < m-j; jj++)
					{						
						offsety = matrixy[j + jj] - matrixy[j];
						//if (offsety > 0 && ans > (matrixy[m - 1] - matrixy[j] + 1) / offsety) { break; }
						indexx = i; indexy = j;
						count = 0;
						while (indexx < n && indexy < m)
						{
							if (offsetx == 0){
								count += matrix[indexx][indexy];
								indexy ++;
							}
							else if (offsety == 0){
								count += matrix[indexx][indexy];
								indexx++;
							}
							else{
								temp = (matrixx[indexx] - matrixx[i]);
								if ((temp * offsety) % offsetx != 0) {indexx++;continue;}
								y =(temp * offsety) / offsetx + matrixy[j];
								if (y <= matrixy[m-1] && ymap.find(y) != ymap.end())
								{
									indexy = ymap[y];
									count += matrix[indexx][indexy];
								}
								indexx++;
							}

						}
						ans = max(ans, count);
						//if (offsetx != 0 && ans >= (matrixx[n - 1] - matrixx[i] + 1) / offsetx) { break; }
					}
				}

			}
		}
		return ans;
	}
};