哈希算法题目：设计完美矩形
字数 2241 2025-12-11 17:02:55

哈希算法题目：设计完美矩形

题目描述

给你一个数组 rectangles，其中 rectangles[i] = [xi1, yi1, xi2, yi2] 表示一个矩形在二维平面上的位置，其中 (xi1, yi1) 是该矩形左下角的坐标，(xi2, yi2) 是该矩形右上角的坐标。你需要判断这些矩形是否恰好覆盖一个完整的矩形区域（即“完美矩形”）。
要求：

  1. 所有矩形之间不重叠（但可以相邻）。
  2. 所有矩形恰好覆盖一个完整的矩形区域，没有空缺，没有超出覆盖。

解题思路

这个问题可以转化为几何条件与哈希表统计的结合。关键在于如何用哈希表高效判断“恰好覆盖一个矩形区域”。核心思路是：

  1. 面积条件：所有小矩形的总面积必须等于最终覆盖的完整矩形的面积。
  2. 顶点条件：最终完整矩形的四个顶点，在全部小矩形的顶点统计中，必须只出现一次；而其他内部顶点（两个或四个矩形的交点）必须出现偶数次（2次或4次）。

为什么？

  • 每个小矩形贡献四个顶点。
  • 在拼接成大矩形时，内部的顶点会被相邻矩形共享，因此每个内部顶点会被计算偶数次。
  • 大矩形的四个角顶点只会被一个矩形贡献，出现奇数次（这里用奇偶判断更简单：出现一次为奇数，内部顶点出现次数为偶数）。

这样，可以用哈希表（或 unordered_map）来记录每个顶点出现的次数，最后检查是否只有四个顶点出现奇数次，且它们正好是大矩形的四个角。

步骤详解

步骤 1：初始化变量

  • 设 totalArea = 0 累计小矩形总面积。
  • 设 minX, minY, maxX, maxY 记录最终大矩形的边界（初始为极值）。
  • 用一个哈希表 vertexCount 来记录每个顶点出现的次数。顶点用 (x, y) 对表示，可用 string 或 pair<int, int> 作为 key。

步骤 2：遍历所有小矩形

对每个矩形 [x1, y1, x2, y2]：

  1. 更新总面积：totalArea += (x2 - x1) * (y2 - y1)。
  2. 更新大矩形边界：
    minX = min(minX, x1)
    maxX = max(maxX, x2)
    minY = min(minY, y1)
    maxY = max(maxY, y2)
  3. 将此矩形的四个顶点加入哈希表：
    • 左下 (x1, y1)
    • 右下 (x2, y1)
    • 左上 (x1, y2)
    • 右上 (x2, y2)
      每个顶点出现次数 +1（如果已存在）或设为 1（首次出现）。

步骤 3：计算大矩形面积

  • 大矩形面积 = (maxX - minX) * (maxY - minY)。
  • 如果 totalArea != 大矩形面积，直接返回 false（面积不等，说明有重叠或空缺）。

步骤 4：检查顶点奇偶性

  • 大矩形的四个角顶点应为：
    (minX, minY)、(minX, maxY)、(maxX, minY)、(maxX, maxY)。
  • 遍历哈希表，统计出现次数为奇数的顶点。
  • 必须恰好有 4 个奇数顶点，且这 4 个顶点正好是上面四个角顶点（位置匹配）。
    如果奇数顶点数不是 4，或者四个角顶点中有任何一个出现次数为偶数，则返回 false。

步骤 5：返回结果

满足以上所有条件，返回 true。

示例演示

输入：rectangles = [[1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]]

  1. 总面积 = 4 + 2 + 2 + 1 + 1 = 10。
  2. 大矩形边界：minX=1, maxX=4, minY=1, maxY=4 → 面积 = 3×3=9。
    发现 10 ≠ 9 → 返回 false（实际例子中这是错的，我们先按正确逻辑走，下面给正确例子）。

正确例子：rectangles = [[1,1,3,3], [3,1,4,3], [1,3,3,4], [3,3,4,4]]（四个矩形拼成 3×3 大矩形）

  1. 总面积 = 4 + 2 + 2 + 1 = 9。
  2. 大矩形边界：minX=1, maxX=4, minY=1, maxY=4 → 面积 = 3×3=9，面积相等。
  3. 顶点统计（简化表示）：
    • (1,1) 1次
    • (3,1) 2次
    • (4,1) 1次
    • (1,3) 2次
    • (3,3) 4次
    • (4,3) 2次
    • (1,4) 1次
    • (3,4) 2次
    • (4,4) 1次
      奇数顶点：(1,1)、(4,1)、(1,4)、(4,4) → 正好四个角，且与大矩形角一致。
  4. 返回 true。

关键细节

  • 顶点去重：同一个顶点在不同矩形中可能被重复添加，所以用哈希表计数，而不是集合。
  • 面积相等是必要条件，但不是充分条件：可能出现面积相等但重叠或空缺的情况，所以需要顶点奇偶性检查。
  • 哈希函数：如果直接用 pair<int,int> 作为 key，需要自定义哈希函数（在 C++ 中），或者转为 string 如 "x,y" 作为 key。

复杂度分析

  • 时间：O(N)，N 是矩形个数，每个矩形处理 4 个顶点。
  • 空间：O(N)，存储顶点计数。

总结

本题是哈希表在几何覆盖问题中的典型应用，核心是通过顶点出现次数的奇偶性来判断是否恰好形成完整矩形，结合面积验证，高效且巧妙地避免了复杂的几何计算。

哈希算法题目：设计完美矩形 题目描述 给你一个数组 rectangles ，其中 rectangles[i] = [xi1, yi1, xi2, yi2] 表示一个矩形在二维平面上的位置，其中 (xi1, yi1) 是该矩形左下角的坐标， (xi2, yi2) 是该矩形右上角的坐标。你需要判断这些矩形是否恰好覆盖一个完整的矩形区域（即“完美矩形”）。 要求 ： 所有矩形之间 不重叠 （但可以相邻）。 所有矩形恰好覆盖一个完整的矩形区域， 没有空缺 ， 没有超出覆盖 。 解题思路 这个问题可以转化为 几何条件 与 哈希表统计 的结合。关键在于如何用哈希表高效判断“恰好覆盖一个矩形区域”。核心思路是： 面积条件 ：所有小矩形的总面积必须等于最终覆盖的完整矩形的面积。 顶点条件 ：最终完整矩形的四个顶点，在全部小矩形的顶点统计中，必须 只出现一次 ；而其他内部顶点（两个或四个矩形的交点）必须出现 偶数次 （2次或4次）。 为什么？ 每个小矩形贡献四个顶点。 在拼接成大矩形时，内部的顶点会被相邻矩形共享，因此每个内部顶点会被计算偶数次。 大矩形的四个角顶点只会被一个矩形贡献，出现奇数次（这里用奇偶判断更简单：出现一次为奇数，内部顶点出现次数为偶数）。 这样，可以用哈希表（或 unordered_map ）来记录每个顶点出现的次数，最后检查是否只有四个顶点出现奇数次，且它们正好是大矩形的四个角。 步骤详解 步骤 1：初始化变量 设 totalArea = 0 累计小矩形总面积。 设 minX, minY, maxX, maxY 记录最终大矩形的边界（初始为极值）。 用一个哈希表 vertexCount 来记录每个顶点出现的次数。顶点用 (x, y) 对表示，可用 string 或 pair<int, int> 作为 key。 步骤 2：遍历所有小矩形 对每个矩形 [x1, y1, x2, y2] ： 更新总面积： totalArea += (x2 - x1) * (y2 - y1) 。 更新大矩形边界： minX = min(minX, x1) maxX = max(maxX, x2) minY = min(minY, y1) maxY = max(maxY, y2) 将此矩形的四个顶点加入哈希表： 左下 (x1, y1) 右下 (x2, y1) 左上 (x1, y2) 右上 (x2, y2) 每个顶点出现次数 +1（如果已存在）或设为 1（首次出现）。 步骤 3：计算大矩形面积 大矩形面积 = (maxX - minX) * (maxY - minY) 。 如果 totalArea != 大矩形面积 ，直接返回 false （面积不等，说明有重叠或空缺）。 步骤 4：检查顶点奇偶性 大矩形的四个角顶点应为： (minX, minY) 、 (minX, maxY) 、 (maxX, minY) 、 (maxX, maxY) 。 遍历哈希表，统计出现次数为奇数的顶点。 必须 恰好有 4 个奇数顶点 ，且这 4 个顶点正好是上面四个角顶点（位置匹配）。 如果奇数顶点数不是 4，或者四个角顶点中有任何一个出现次数为偶数，则返回 false 。 步骤 5：返回结果 满足以上所有条件，返回 true 。 示例演示 输入： rectangles = [[1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]] 总面积 = 4 + 2 + 2 + 1 + 1 = 10。 大矩形边界： minX=1, maxX=4, minY=1, maxY=4 → 面积 = 3×3=9。 发现 10 ≠ 9 → 返回 false （实际例子中这是错的，我们先按正确逻辑走，下面给正确例子）。 正确例子 ： rectangles = [[1,1,3,3], [3,1,4,3], [1,3,3,4], [3,3,4,4]] （四个矩形拼成 3×3 大矩形） 总面积 = 4 + 2 + 2 + 1 = 9。 大矩形边界： minX=1, maxX=4, minY=1, maxY=4 → 面积 = 3×3=9，面积相等。 顶点统计（简化表示）： (1,1) 1次 (3,1) 2次 (4,1) 1次 (1,3) 2次 (3,3) 4次 (4,3) 2次 (1,4) 1次 (3,4) 2次 (4,4) 1次 奇数顶点：(1,1)、(4,1)、(1,4)、(4,4) → 正好四个角，且与大矩形角一致。 返回 true 。 关键细节 顶点去重 ：同一个顶点在不同矩形中可能被重复添加，所以用哈希表计数，而不是集合。 面积相等是必要条件，但不是充分条件 ：可能出现面积相等但重叠或空缺的情况，所以需要顶点奇偶性检查。 哈希函数 ：如果直接用 pair<int,int> 作为 key，需要自定义哈希函数（在 C++ 中），或者转为 string 如 "x,y" 作为 key。 复杂度分析 时间：O(N)，N 是矩形个数，每个矩形处理 4 个顶点。 空间：O(N)，存储顶点计数。 总结 本题是哈希表在几何覆盖问题中的典型应用，核心是通过顶点出现次数的奇偶性来判断是否恰好形成完整矩形，结合面积验证，高效且巧妙地避免了复杂的几何计算。