按距离统计房屋对数目 I

标签: 广度优先搜索 图 前缀和

难度: Medium

给你三个 正整数 n 、x 和 y 。

在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house1, house2] ，即从 house1 到 house2 需要经过的 最少 街道数为 k 。

返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。

注意，x 与 y 可以 相等 。

示例 1：

输入：n = 3, x = 1, y = 3
输出：[6,0,0]
解释：让我们检视每个房屋对
- 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。
- 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。
- 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。
- 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。
- 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。
- 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。

示例 2：

输入：n = 5, x = 2, y = 4
输出：[10,8,2,0,0]
解释：对于每个距离 k ，满足要求的房屋对如下：
- 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。
- 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。
- 对于 k == 3，满足要求的房屋对有 (1, 5)，以及 (5, 1) 。
- 对于 k == 4 和 k == 5，不存在满足要求的房屋对。

示例 3：

输入：n = 4, x = 1, y = 1
输出：[6,4,2,0]
解释：对于每个距离 k ，满足要求的房屋对如下：
- 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。
- 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。
- 对于 k == 3，满足要求的房屋对有 (1, 4), 以及 (4, 1)。
- 对于 k == 4，不存在满足要求的房屋对。

提示：

  • 2 <= n <= 100
  • 1 <= x, y <= n

Submission

运行时间: 40 ms

内存: 16.1 MB

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        # 调整 x, y 的大小关系
        if x > y: 
            x, y = y, x
        ans = [0] * (n + 1)
        x -= 1
        y -= 1
        for i in range(n):
            # 不需要中介
            if abs(i - x) + 1 > abs(i - y):
                ans[1] += 1
                ans[n - i] -= 1
            # 需要中介
            else:
                d = abs(i - x) + 1
                sep = i + d + (y - i - d) // 2
                ans[1] += 1
                ans[sep - i + 1] -= 1
                ans[d + 1] += 1
                ans[d + y - sep] -= 1
                ans[d] += 1
                ans[d + n - y] -= 1
        ans = list(accumulate(ans))
        return [x * 2 for x in ans[1:]]

Explain

此题解采用了前缀和的思想。首先，通过调整 x, y 的大小关系，保证 x < y。然后遍历每个房屋，对于每个房屋 i，计算从 i 到 x 和从 i 到 y 的距离，根据这两个距离的大小关系，判断房屋对是否需要通过街道 x 到 y 的中介。在确定了是否需要中介后，对结果数组进行更新，最后通过累加前缀和，计算每个距离下的房屋对数量。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if x > y: 
            x, y = y, x
        ans = [0] * (n + 1)
        x -= 1
        y -= 1
        for i in range(n):
            if abs(i - x) + 1 > abs(i - y):
                ans[1] += 1
                ans[n - i] -= 1
            else:
                d = abs(i - x) + 1
                sep = i + d + (y - i - d) // 2
                ans[1] += 1
                ans[sep - i + 1] -= 1
                ans[d + 1] += 1
                ans[d + y - sep] -= 1
                ans[d] += 1
                ans[d + n - y] -= 1
        ans = list(accumulate(ans))
        return [x * 2 for x in ans[1:]]

Explore

在算法中确保 x < y 的主要原因是为了简化问题处理逻辑和保持一致性。当 x < y 时，可以统一地处理所有房屋到街道 x 和 y 的距离比较，而不需要在每次比较时都考虑 x 和 y 的相对位置。这样可以减少代码的复杂性并避免出错。此外，算法中的计算步骤和更新操作可以按照固定的方向（从 x 到 y）执行，这有助于减少条件判断，使算法更加清晰和高效。

在题解中，我们通过比较从房屋 i 到 x 和从房屋 i 到 y 的距离来决定是否需要通过街道 x 到 y 的中介。基本原理是，如果房屋到 x 的距离加上从 x 到 y 的距离（即绕路的总距离）大于直接从房屋到 y 的距离，那么可以认为房屋 i 更倾向于直接连接到 y，而不通过 x。这种判断帮助我们理解房屋对的连接方式如何依赖于其到两条街道的相对位置。

题解中的更新操作使用了一种差分数组的方法来高效地管理区间更新。`ans[1] += 1`意味着从距离 1 开始，房屋对数量增加。而`ans[n - i] -= 1`表示在距离 n-i 处房屋对数量减少，这是因为超出这个距离后，之前增加的房屋对不再在计数范围内。通过这种方法，我们可以在 O(1) 的时间复杂度内更新大范围的数据，最后通过累加这些差分值来还原出每个距离下的实际房屋对数量。这种技术极大地提高了数据更新的效率，特别是在处理大量数据时。