正方形中的最多点数

2024-05-15 Java, 位运算, 排序, 算法字数统计: 1.4k(字)

这是我在 LeetCode 周赛中碰到的一道题，当时做的很费劲，但也是做出来，之后看了灵神的题解，发现这题的解法还是很多的，也很有意思，可以去详细研究一下。

题目描述

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

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

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

注意：

如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
正方形的边长可以为零。

示例

输入： points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = “abdca”

输出： 2

解释：

边长为 4 的正方形包含两个点 points[0] 和 points[1] 。

解析 1（逐步扩圈）

正方形从零逐步扩大，一旦有重复的标签，就返回这一圈以内的点的个数。

使用 Pair 类存储点的坐标、最大边长和标签，利用最大边长排序后，用双指针进行遍历，左指针 left 指向正方形相等距离的最左边，右指针 right 不断向右移动，遇到重复标签，返回左指针索引 (left+1)-1 也就是 left。

参考 1

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int n = points.length;
        Set<Character> set = new HashSet<>();
        
        Pair[] pairs = new Pair[n];
        for (int i = 0; i < n; i++) {
            pairs[i] = new Pair(points[i][0], points[i][1], s.charAt(i));
        }

        Arrays.sort(pairs, (o1, o2) -> o1.distance - o2.distance);

        int l = 0, r = 0;
        while (r < n){
            while (r < n && pairs[l].distance == pairs[r].distance){
                if(!set.add(pairs[r].c)) return l;
                r++;
            }
            l = r;
        }

        return n;
    }

    class Pair{
        int i;
        int j;
        char c;
        int distance;
        public Pair(int i, int j, char c){
            this.i = i;
            this.j = j;
            this.c = c;
            this.distance = Math.max(Math.abs(i), Math.abs(j));
        }
    }
}

时间复杂度:
排序时间复杂度 O(nlogn)

空间复杂度:
使用 Pair 数组存储 O(n)

解析 2（二分查找 + 位运算）

第一种思路是利用排序，逐步遍历，从而找到正方形，这种解法的效率不是不是最佳。

可以利用二分查找，去检查是否有重复的标签

如果没有重复的标签，正方形合法，则继续扩大；

如果有重复的标签，正方形不合法，缩小正方形

此外，在检查是否有重复标签时，可以用位运算来优化，因为最多只有 26 个标签（小写字母），所有可以用位运算来代替 HashSet，优化空间。

具体步骤：

通过 s[i] - 'a' 获取标签的 c 掩码位置
利用 vis |= 1 << c 将 c 加入集合中
通过 (vis >> c & 1) > 0 检查之后的标签是否重复，如果重复直接返回 false。

参考

class Solution {
    private int ans;

    public int maxPointsInsideSquare(int[][] points, String S) {
        char[] s = S.toCharArray();
        int left = -1;
        int right = 1_000_000_001;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(mid, points, s)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return ans;
    }

    boolean check(int size, int[][] points, char[] s) {
        int vis = 0;
        for (int i = 0; i < points.length; i++) {
            // 判断点是否在正方形中
            if (Math.abs(points[i][0]) <= size && Math.abs(points[i][1]) <= size) {
                int c = s[i] - 'a';
                if ((vis >> c & 1) > 0) { // c 在集合中
                    return false;
                }
                vis |= 1 << c; // 把 c 加入集合
            }
        }
        ans = Integer.bitCount(vis);
        return true;
    }
}

时间复杂度：

O(nlogn)，二分查找的复杂度为 O(logn)，每次检查的复杂度为 O(n)

空间复杂度：

O(1)

解析 3（维护标签的最小距离和次小距离的最小值）

在开始之前，先介绍一下切比雪夫距离

切比雪夫距离： 向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值

定义点 (x1, y1) 到 (x2, y2) 的距离为 max{|x1 - x2|, |y1 - y2|}

定义一个数组 minD，用于存储每种标签的最小距离。

定义一个变量 min2，用于存储次小的距离

具体步骤：

遍历所有点，计算每个点切比雪夫距离
如果当前距离小于数组中距离，更新数组 minD[c] 与次小距离 min2
否则，只更新次小距离 min2
遍历数组 minD，计数小于次小距离的标签，即 minD[c] < min2

通过计算每个字符到原点的最小距离和次小距离,确定可以包含在边长为次小距离的正方形内的不同字符的数量。最终返回的结果是可以包含在这个正方形内的不同字符的最大数量。

参考 3

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int[] minD = new int[26];
        Arrays.fill(minD, Integer.MAX_VALUE);
        int min2 = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            int d = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
            int c = s.charAt(i) - 'a';
            if (d < minD[c]) {
                // d 是目前最小的，那么 minD[c] 是次小的
                min2 = Math.min(min2, minD[c]);
                minD[c] = d;
            } else {
                // d 可能是次小的
                min2 = Math.min(min2, d);
            }
        }
        int ans = 0;
        for (int d : minD) {
            if (d < min2) {
                ans++;
            }
        }
        return ans;
    }
}

时间复杂度：

O(n)

空间复杂度：

O(1)

yzlzzz

developer