[M二分] lc3143. 正方形中的最多点数(二分答案+代码实现+模拟)

文章目录

• • 1. 题目来源
  • 2. 题目解析

1. 题目来源

链接：3143. 正方形中的最多点数

2. 题目解析

模拟是一个比较常见的思路，代码写的也算顺利吧，有一些条件没有考虑清楚，WA 4 次… 有点可惜。
模拟重点：

• 针对重复的点，需要用双指针的思想进行判断并剔除哈，不然只用下标 i 会少判断很多点。

在这里重点看看如何 二分答案 吧，一些有经验的选手，第一反映反而是 二分答案。题感较差，在本题并没有采用：

• 边长越长，我们能够纳入的点会越多。越多肯定是对我们情况越有利。
• 当边长内存在重复点时，说明需要一个更短的边，避免重复。
• 综上，可以直接对边长进行 二分答案，找到一个最大的、满足正方形内无重复点的正方形即可。

二分答案是一种算法思维哈，着重关注下。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$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);     } };