LeetCode 835. 图像重叠

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 网易
标签
数组 矩阵

题目描述

✅ 835. 图像重叠

image-20260929104919657

image-20260929104919787

image-20260929104919984

题意分析

两张图像都是 n × n 的二值矩阵，只允许把其中一张整体平移，不能旋转。统计平移后两图同时为 1 的格子数并求最大值；移出边界的部分被丢弃，两个 0 重合不算贡献。

解法：点对差向量计数

核心思路

[!blue]

一次整体平移由行偏移、列偏移两个数决定。若第一张图中的 1 位于 a，第二张图中的 1 位于 b，让它们重合的唯一平移向量就是 b - a。因此可以反过来枚举所有 1 的点对，给对应位移计数，而不用真的移动整张矩阵。

固定一个位移后，每个第一张图的点都会到达唯一坐标，所以至多与第二张图的一个点匹配；反过来，每个重叠格也唯一确定一对原始坐标。因此某个位移出现的点对数，恰好等于这次整体平移的重叠数，不会重复统计同一个格子。

先提取两图中所有 1 的坐标，再用哈希表统计完整的二维差向量。Java 把行差放入 long 的高 32 位、列差的位模式放入低 32 位，两部分互不干扰；Go 直接使用 [2]int 作为键。不能只记录一维差，负方向的位移也要正常保留。

每次增加某个位移的计数时更新最大值。移出边界的点找不到第二张图中的匹配坐标，自然不会贡献，无需额外裁剪；若任意一图没有 1，点对循环不执行，答案保持 0。

解题步骤

  1. 提取两个图像中值为一的坐标。
  2. 枚举两侧点对，计算固定方向的行列差。
  3. 以完整二维差向量作为键累加次数。
  4. 每次更新计数时维护最大值。

代码实现

class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        List<int[]> a = new ArrayList<>();
        List<int[]> b = new ArrayList<>();
        int n = img1.length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (img1[i][j] == 1) {
                    a.add(new int[] {
                        i,
                        j
                    });
                }

                if (img2[i][j] == 1) {
                    b.add(new int[] {
                        i,
                        j
                    });
                }
            }
        }

        Map<Long, Integer> cnt = new HashMap<>();
        int answer = 0;

        for (int[] pa : a) {
            for (int[] pb : b) {
                int dx = pb[0] - pa[0];
                int dy = pb[1] - pa[1];
                // 完整记录二维差向量，避免不同平移被合并。
                long key = (((long) dx) << 32) ^ (dy & 0xffffffffL);
                // 同一个差向量的点对数，就是该平移下的重叠数。
                int v = cnt.getOrDefault(key, 0) + 1;

                cnt.put(key, v);
                answer = Math.max(answer, v);
            }
        }

        return answer;
    }
}

type Point struct{ x, y int }

func largestOverlap(img1 [][]int, img2 [][]int) int {
    a := make([]Point, 0)
    b := make([]Point, 0)
    n := len(img1)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if img1[i][j] == 1 {
                a = append(a, Point{x: i, y: j})
            }
            if img2[i][j] == 1 {
                b = append(b, Point{x: i, y: j})
            }
        }
    }

    cnt := make(map[[2]int]int)
    answer := 0
    for _, pa := range a {
        for _, pb := range b {
            dx := pb.x - pa.x
            dy := pb.y - pa.y
            // 完整记录二维差向量，避免不同平移被合并。
            key := [2]int{
                dx,
                dy,
            }
            // 同一个差向量的点对数，就是该平移下的重叠数。
            cnt[key]++
            if cnt[key] > answer {
                answer = cnt[key]
            }
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n^2+pq)$，p、q 为两图中一的数量。
  • 空间复杂度：设实际不同差向量数为 D，空间为 $O(p+q+D+1)$，其中 $D≤\min(pq,(2n-1)^2)$，包含坐标列表和偏移计数表。

关键点总结

[!green]

  • 计数键必须同时包含行差和列差。
  • 平移方向前后一致即可，负位移同样合法。
  • 全零图像没有点对，答案自然保持零。

易错点总结

[!yellow]

  • 只记录一维差值：不同平移被混在一起。
  • 无分隔符拼接两维数字：不同坐标对可能形成相同字符串键，必须使用不会混淆两维的表示。
  • 把两边都为零也计入重叠：题目只统计一格。
  • 只枚举非负位移：漏掉向上、向左移动的可能。

相似题目

题目 难度 关联与区别
447. 回旋镖的数量 中等 同样按点对几何特征计频次，本题按两图1点之间的位移向量分组，原题按到锚点的距离分组。
311. 稀疏矩阵的乘法 中等 只枚举值为1或非零的位置可减少无效组合，本题对各位移累计匹配点数，原题累计乘积。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/19621818
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！