Hard

题目描述

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

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

对于每个 k（1 <= k <= n），你需要找出满足以下条件的房屋对 (house1, house2) 的数目：从 house1 到 house2 需要经过的 最少 街道数为 k。

返回一个长度为 n 的从 1 开始索引的数组 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]

示例 3：

输入：n = 4, x = 1, y = 1
输出：[6,4,2,0]

提示：

  • 2 <= n <= 10^5
  • 1 <= x, y <= n

解题思路

这道题的核心思想是分析额外边（x-y）对房屋间距离的影响。

分析思路：

  1. 基础情况：如果没有额外的 x-y 边，房屋 i 和 j 之间的最短距离就是 |i-j|，距离为 k 的房屋对数为 2×(n-k)。

  2. 额外边的影响：额外边 x-y 可能会缩短某些房屋对之间的距离。对于房屋 i 和 j，它们之间有两条可能的路径：

    • 直接路径：|i-j|
    • 经过额外边的路径：|i-x| + 1 + |y-j| 或 |i-y| + 1 + |x-j|

  3. 距离变化分析：我们需要统计有多少房屋对的最短距离因为额外边而发生了变化，以及变化的幅度。

  4. 优化计算：为了避免 O(n²) 的复杂度，我们使用数学推导和前缀和技术来批量计算距离变化。

算法步骤：

  1. 首先计算没有额外边时的距离分布
  2. 分析额外边对不同区间房屋对距离的影响
  3. 使用差分数组技术批量更新距离计数
  4. 最终得到每个距离对应的房屋对数量

这种方法将时间复杂度优化到 O(n)，适合处理大规模数据。

代码实现

class Solution {
public:
    vector<long long> countOfPairs(int n, int x, int y) {
        if (x > y) swap(x, y);
        
        vector<long long> result(n, 0);
        
        // 基础情况：没有额外边时的距离分布
        for (int d = 1; d <= n - 1; d++) {
            result[d - 1] = 2LL * (n - d);
        }
        
        // 如果 x == y，额外边没有意义
        if (x == y) return result;
        
        // 计算额外边的影响
        int gap = y - x - 1;  // x 和 y 之间原有路径的内部节点数
        
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int orig_dist = j - i;
                int new_dist1 = abs(i - x) + 1 + abs(j - y);
                int new_dist2 = abs(i - y) + 1 + abs(j - x);
                int new_dist = min(new_dist1, new_dist2);
                
                if (new_dist < orig_dist) {
                    result[orig_dist - 1] -= 2;
                    result[new_dist - 1] += 2;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if x > y:
            x, y = y, x
        
        result = [0] * n
        
        # 基础情况：没有额外边时的距离分布
        for d in range(1, n):
            result[d - 1] = 2 * (n - d)
        
        # 如果 x == y，额外边没有意义
        if x == y:
            return result
        
        # 计算额外边的影响
        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                orig_dist = j - i
                new_dist1 = abs(i - x) + 1 + abs(j - y)
                new_dist2 = abs(i - y) + 1 + abs(j - x)
                new_dist = min(new_dist1, new_dist2)
                
                if new_dist < orig_dist:
                    result[orig_dist - 1] -= 2
                    result[new_dist - 1] += 2
        
        return result

public class Solution {
    public long[] CountOfPairs(int n, int x, int y) {
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        
        long[] result = new long[n];
        
        // 基础情况：没有额外边时的距离分布
        for (int d = 1; d <= n - 1; d++) {
            result[d - 1] = 2L * (n - d);
        }
        
        // 如果 x == y，额外边没有意义
        if (x == y) return result;
        
        // 计算额外边的影响
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int origDist = j - i;
                int newDist1 = Math.Abs(i - x) + 1 + Math.Abs(j - y);
                int newDist2 = Math.Abs(i - y) + 1 + Math.Abs(j - x);
                int newDist = Math.Min(newDist1, newDist2);
                
                if (newDist < origDist) {
                    result[origDist - 1] -= 2;
                    result[newDist - 1] += 2;
                }
            }
        }
        
        return result;
    }
}

var countOfPairs = function(n, x, y) {
    if (x > y) [x, y] = [y, x];
    
    const result = new Array(n).fill(0);
    
    if (x === y) {
        // No additional edge, just a line
        for (let i = 1; i <= n; i++) {
            for (let j = i + 1; j <= n; j++) {
                const dist = j - i;
                result[dist - 1] += 2;
            }
        }
        return result;
    }
    
    for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
            // Distance via normal path (line)
            const normalDist = j - i;
            
            // Distance via shortcut (x, y)
            const shortcutDist = Math.abs(i - x) + 1 + Math.abs(j - y);
            const shortcutDist2 = Math.abs(i - y) + 1 + Math.abs(j - x);
            
            const minDist = Math.min(normalDist, shortcutDist, shortcutDist2);
            result[minDist - 1] += 2;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型当前解法优化解法
时间复杂度O(n²)O(n)
空间复杂度O(1)O(1)

说明：

  • 当前解法使用双重循环计算所有房屋对，时间复杂度为 O(n²)
  • 更优化的解法可以通过数学推导和差分数组技术将时间复杂度降到 O(n)
  • 空间复杂度为 O(1)（不计算输出数组）

相关题目