力扣——3143.正方形中的最多点数

题目：

自己的题解（史）：

PS：自己看了好几遍才看懂题目，然后想看题解，但是又看到了“标签”是
于是靠着自己效率极低的写了出来。

思路：二分

首先利用map，将每个坐标和标签进行哈希对应。
然后找到正方形的最大值，即坐标中数值最大的数字（这里有个坑，要注意负数的存在）最后二分确定正方形的边界值，判断条件是利用set查看里面的坐标是否存在标签重复。（注意二分算法不要死循环）
确定边界值后，直接循环points数组，看看里面有几个点在边界内就行。

代码：

class Solution {
public:int maxPointsInsideSquare(vector<vector<int>>& points, string s) {// 首先是哈希键值对建立（map<vector<int>,char>）// 二分法来确定正方形的边长（初始为坐标最大的值）// 收缩条件是判断在正方形里的坐标点是否标签唯一（unordered_set）int maxl = 0;map<vector<int>, char> m;int len = points.size();for (int i = 0; i < len; i++) {m.insert(make_pair(points[i], s[i]));int t1, t2;   //易错！！要考虑复数之间的大小比较if (points[i][0] < 0)t1 = -points[i][0];elset1 = points[i][0];if (points[i][1] < 0)t2 = -points[i][1];elset2 = points[i][1];int tmp = t1 > t2 ? t1 : t2;maxl = maxl > tmp ? maxl : tmp;}int left = 0, right = maxl, mid;while (left < right) {mid = left + (right - left + 1) / 2; //?怎么才能不写成死循环？// 判断符合吗bool fuhe = true;unordered_set<char> se;for (int i = 0; i < len; i++) {if (points[i][0] <= mid && points[i][0] >= -mid &&points[i][1] <= mid && points[i][1] >= -mid) {if (se.find(m[points[i]]) == se.end()) {se.insert(m[points[i]]);} else {fuhe = false;break;}}}if (fuhe) {left = mid;} else {right = mid - 1;}}int jieguo = 0;for (int i = 0; i < len; i++) {if (points[i][0] <= left && points[i][0] >= -left &&points[i][1] <= left && points[i][1] >= -left) {jieguo++;}}return jieguo;}
};

复杂度

结果：

官方题解：

思路：维护次小距离的最小值

定义正方形的半径：
- 正方形的半径定义为边长的一半。
- 每个点 (x,y)(x, y)(x,y) 所在正方形的半径为点 (x,y)(x, y)(x,y) 到原点 (0,0)(0, 0)(0,0) 的「切比雪夫距离」，即 max⁡(∣x∣,∣y∣)\max(\lvert x \rvert, \lvert y \rvert)max(∣x∣,∣y∣)。
计算最小半径和次小半径：
- 对于每个字符，计算字符到原点的最小的半径，并维护所有字符的次小半径。
- 如果一个字符的半径小于次小半径，那么这个字符所对应的点可以放在合法正方形内。
合法正方形的定义：
- 对于每个字符，如果其半径小于次小半径，那么它可以在合法正方形内。
统计合法正方形内的点数：
- 最后遍历所有字符的最小距离，返回在合法正方形内的点数。

代码：

class Solution {
public:int maxPointsInsideSquare(vector<vector<int>>& points, string s) {// 用于存储每个字符的最小半径，初始为一个很大的数vector<int> min1(26, 1000000001);// 用于存储所有字符的次小半径，初始为一个很大的数int min2 = 1000000001;// 字符串的长度，即点的数量int n = s.length();// 遍历每个点，计算其半径并更新最小半径和次小半径for (int i = 0; i < n; ++i) {int x = points[i][0], y = points[i][1], j = s[i] - 'a';// 计算点到原点的切比雪夫距离int d = max(abs(x), abs(y));if (d < min1[j]) {// 如果当前半径小于最小半径，更新次小半径并设置新的最小半径min2 = min(min2, min1[j]);min1[j] = d;} else if (d < min2) {// 如果当前半径介于最小半径和次小半径之间，更新次小半径min2 = d;}}// 统计合法正方形内的点数int res = 0;for (int d : min1) {if (d < min2) {++res;}}return res;}
};