题解 | 正方形中的最多点数

题干分析:

一个以坐标系原点为中心正方形能够容纳多少个标号不同的坐标点,同时要求这些坐标点不能有标号相同的.

首先我们观察到整个过程在整数集下进行讨论,因此正方形的增长为离散的,且大的正方形包含小正方形,因此可以进行逐个大小的正方形计数,直到计数发现有标号重复的点为止.

算法逻辑:

承接初步的思路,为了让我们能够对正方形大小进行枚举计数,我们需要明白在正方形上的点的特征,这里特征很明显,便是相应点的坐标值的绝对值的最大值便是经过该点的正方形大小.同时为了让我们进行逐大小计数,我们需要进行排序.此后直接按照原想法计数即可.

实现代码:

int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        const int n = static_cast<int>(points.size());
        for (int i = 0; i < n; ++i) { // 初期处理,第一个值变为正方形大小,第二个值为标号索引
            points[i][0] = max(abs(points[i][0]), abs(points[i][1]));
            points[i][1] = s[i] - 'a';
        }
    
  		// 自定义排序
        ranges::sort(points, [&](const vector<int> &a, const vector<int> &b) -> bool {
            return a[0] < b[0];
        });
    
        int ans = 0;
        int has = 0; // 这里用位存储是否存在该标点,节省空间
        int size = points[0][0];
        auto it = points.begin();
  		// 符合要求才计数(it不指向最后,且标号暂时不存) 
        while (it != points.end() && !(has >> (*it)[1] & 1)) {
            int temp = 0; // 计数当前大小正方形上点的数目
            while (it != points.end() && size == (*it)[0] && !(has >> (*it)[1] & 1)) {
                ++temp;
                has |= 1 << (*it)[1];
                ++it;
            }
		  	// 到达最后,正方形仍旧符合,加入总数同时退出循环
            if (it == points.end()) {
                ans += temp;
                break;
            }
		  	// 出内循环时该大小正方形已计数完毕,记录值并更新大小,不然不符合便不计入总数
            if (size != (*it)[0]) {
                ans += temp;
                size = (*it)[0];
            }
        }
    
        return ans;
    }

复杂度分析:

• 时间复杂度: 排序O(nlog n), 枚举O(n)(依据it,整个过程只有内循环更改it,且it只从数头部移动到数组尾部),总计O(nlog n).
• 空间复杂度: 排序O(log n)的运行栈空间, 其余只使用到常数额外空间,总计O(log n).