[M二分] lc3143. 正方形中的最多点数(二分答案+代码实现+模拟)
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:3143. 正方形中的最多点数
2. 题目解析
模拟是一个比较常见的思路,代码写的也算顺利吧,有一些条件没有考虑清楚,WA 4 次… 有点可惜。
模拟重点:
- 针对重复的点,需要用双指针的思想进行判断并剔除哈,不然只用下标
i
会少判断很多点。
在这里重点看看如何 二分答案 吧,一些有经验的选手,第一反映反而是 二分答案。题感较差,在本题并没有采用:
- 边长越长,我们能够纳入的点会越多。越多肯定是对我们情况越有利。
- 当边长内存在重复点时,说明需要一个更短的边,避免重复。
- 综上,可以直接对边长进行 二分答案,找到一个最大的、满足正方形内无重复点的正方形即可。
二分答案是一种算法思维哈,着重关注下。
- 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度: O ( n ) O(n) O(n)
模拟写法:
class Solution {
public:int maxPointsInsideSquare(vector<vector<int>>& points, string s) {int n = points.size();vector<pair<int, char>> l(n);for (int i = 0; i < n; i ++ ) l[i] = {max(abs(points[i][0]), abs(points[i][1])), s[i]};sort(l.begin(), l.end());int res = 0;set<char> S;for (int i = 0; i < n; i ++ ) {int x = l[i].first;char c = l[i].second;if (S.count(c)) return i;S.insert(c);int j = i + 1;while (j < n && x == l[j].first) {char c = l[j].second;if (S.count(c)) return i;S.insert(c);j ++ ;}i = j - 1;}return n;}
};
二分答案:
class Solution {
public:int getPoints(vector<vector<int>>& points, string& s, int r) {int cnt = 0;int n = points.size();set<char> S;for (int i = 0; i < n; i ++ ) {int x = max(abs(points[i][0]), abs(points[i][1]));if (x > r) continue; // 如果边长超出了可提供的范围,则直接 continue 即可char c = s[i]; // 边长内包含的点,均不可重复if (S.count(c)) return -1; // 重复了,边长需要进一步缩小cnt ++ ;S.insert(c);}return cnt; // 未重复,边长可进一步扩大}int maxPointsInsideSquare(vector<vector<int>>& points, string s) {int l = 0, r = 1e9; // 以正方形所有的边界可取范围作为二分范围while (l < r) { // 整数二分模版int mid = l + r + 1 >> 1;if (getPoints(points, s, mid) >= 0) l = mid; // 如果当前的边长能获取到不重复的点,则进一步扩大边长即可else r = mid - 1; // 有冲突的点,则需要缩小范围}// 最终输出最大边长的点的个数return getPoints(points, s, l);}
};