正方形中的最多点数

leetcode

题目：

给你一个二维数组points 和一个字符串s，其中points[i]表示第 i 个点的坐标，s[i]表示第i个点的 标签 。

如果一个正方形的中心在(0, 0)，所有边都平行于坐标轴，且正方形内不存在标签相同的两个点，那么我们称这个正方形是合法的。

请你返回合法正方形中可以包含的最多点数。

注意：

• 如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
• 正方形的边长可以为零。
  提示：
• 1 <= s.length, points.length <= 10^5
• points[i].length == 2
• -10^9 <= points[i][0], points[i][1] <= 10^9
• s.length == points.length
• points 中的点坐标互不相同。
• s只包含小写英文字母。

看到题目后。想到的第一种方法时，遍历points数组，然后将其中的点points[i]与(0, 0)的切比雪夫距离(max(abs(points[i][0]), abs(points[i][1]))作为下标，将s[i]作为值存储到一个二维数组count中。

在遍历完points数组后，从小到大遍历count，同时定义一个visit数组，用于表示标签是否在正方形。在count[i]中查看每个标签是否在正方形中，如果遍历完没有重复的标签，就将cnt加一，如果有重复就退出循环。然后返回cnt。

但因为-10^9 <= points[i][0], points[i][1] <= 10^9，测存储需要的空间太多。

然后想到标签只有26个，因此可以用标签作为下标，切比雪夫距离作为值存储到一个二维数组count中，当遍历完points数组后，将count[i]按从小到大排序，然后比较count[i][0]和count[i][1]，先定义一个Max,代表合法正方形的最大的边长的一半需要小于Max。如果两者相等，则合Max为max(Max,count[i][1])，如果两者不等，则Max为max(Max,count[i][1]).然后在遍历count[i][0]，如果count[i][0]小于Max，则cnt加一。最后返回cnt。

然后再写代码时发现，最后的比较阶段只利用了count[i][0]和count[i][1]，也就是最小切比雪夫距离和次小切比雪夫距离。然后再求Max时，可以直接max(Max,count[i][1])，因为两者相等时，count[i][0]和count[i][1]大小一致。

• c++代码

  vector<vector<int>> count(26,vector<int>(2,INT_MAX));
          for (int i = 0; i < n; i++) 
          {
              int temp = max(abs(points[i][0]), abs(points[i][1]));
              if (temp < count[s[i] - 'a'][0]) 
              {
                  count[s[i] - 'a'][1] = count[s[i] - 'a'][0];
                  count[s[i] - 'a'][0] = temp;
              }
              else if (temp < count[s[i] - 'a'][1])
              {
                  count[s[i] - 'a'][1] = temp;
              }
          }
          int m = INT_MAX;
          for (int i = 0; i < 26; i++) 
          {
              m = min(m, count[i][1]);
          }
          int ans = 0;
          for (int i = 0; i < 26; i++)
          {
              if (count[i][0] < m) 
              {
                  ans++;
              }
          }

再查看题解后还有一种思路是二分查找。

通过二分正方形的边长，每次遍历整个points,如果points[i]不在正方形内，则退出，更新二分的left和right.