Medium

题目描述

给你一个下标从 0 开始、由 n 个整数组成的数组 arr。

arr 中两个元素的间隔定义为它们下标之间的绝对差。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j|。

返回一个长度为 n 的数组 intervals，其中 intervals[i] 是 arr[i] 与 arr 中每个相同值元素之间的间隔之和。

注意：|x| 是 x 的绝对值。

示例 1：

输入：arr = [2,1,3,1,2,3,3]
输出：[4,2,7,2,4,4,5]
解释：
- 下标 0：另一个 2 在下标 4，|0 - 4| = 4
- 下标 1：另一个 1 在下标 3，|1 - 3| = 2  
- 下标 2：另外两个 3 在下标 5 和 6，|2 - 5| + |2 - 6| = 7
- 下标 3：另一个 1 在下标 1，|3 - 1| = 2
- 下标 4：另一个 2 在下标 0，|4 - 0| = 4
- 下标 5：另外两个 3 在下标 2 和 6，|5 - 2| + |5 - 6| = 4
- 下标 6：另外两个 3 在下标 2 和 5，|6 - 2| + |6 - 5| = 5

示例 2：

输入：arr = [10,5,10,10]
输出：[5,0,3,4]
解释：
- 下标 0：另外两个 10 在下标 2 和 3，|0 - 2| + |0 - 3| = 5
- 下标 1：数组中只有一个 5，所以与相同元素的间隔之和为 0
- 下标 2：另外两个 10 在下标 0 和 3，|2 - 0| + |2 - 3| = 3  
- 下标 3：另外两个 10 在下标 0 和 2，|3 - 0| + |3 - 2| = 4

约束条件：

  • n == arr.length
  • 1 <= n <= 10^5
  • 1 <= arr[i] <= 10^5

解题思路

这道题的关键在于高效计算每个元素与其他相同值元素的距离之和。暴力解法的时间复杂度为 O(n²)，对于大数据会超时。

核心思路：

  1. 分组处理：首先用哈希表将相同值的元素按下标分组
  2. 前缀和优化：对于每组相同元素，利用前缀和技巧避免重复计算

算法细节：

对于某个值的所有下标 [i₀, i₁, …, iₖ]，当我们计算位置 iⱼ 的距离和时：

  • 左边的贡献：iⱼ × j - (i₀ + i₁ + … + iⱼ₋₁)
  • 右边的贡献：(iⱼ₊₁ + … + iₖ) - iⱼ × (k - j)

通过维护前缀和，可以在 O(1) 时间内计算出每个位置的距离和。

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，能够高效处理大规模数据。

代码实现

class Solution {
public:
    vector<long long> getDistances(vector<int>& arr) {
        int n = arr.size();
        vector<long long> result(n, 0);
        unordered_map<int, vector<int>> groups;
        
        // 按值分组，记录每个值的所有下标
        for (int i = 0; i < n; i++) {
            groups[arr[i]].push_back(i);
        }
        
        // 对每组相同值的元素计算距离和
        for (auto& [val, indices] : groups) {
            int size = indices.size();
            if (size == 1) continue;
            
            // 计算前缀和
            long long prefixSum = 0;
            for (int i = 0; i < size; i++) {
                int idx = indices[i];
                // 计算与左边元素的距离和
                long long leftSum = (long long)idx * i - prefixSum;
                // 计算与右边元素的距离和
                long long totalSum = 0;
                for (int j = 0; j < size; j++) {
                    totalSum += indices[j];
                }
                long long rightSum = (totalSum - prefixSum - idx) - (long long)idx * (size - i - 1);
                
                result[idx] = leftSum + rightSum;
                prefixSum += idx;
            }
        }
        
        return result;
    }
};

class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        n = len(arr)
        result = [0] * n
        groups = defaultdict(list)
        
        # 按值分组，记录每个值的所有下标
        for i, val in enumerate(arr):
            groups[val].append(i)
        
        # 对每组相同值的元素计算距离和
        for indices in groups.values():
            size = len(indices)
            if size == 1:
                continue
            
            # 计算总和和前缀和
            total_sum = sum(indices)
            prefix_sum = 0
            
            for i, idx in enumerate(indices):
                # 左边的贡献：idx * i - prefix_sum
                left_sum = idx * i - prefix_sum
                # 右边的贡献：(total_sum - prefix_sum - idx) - idx * (size - i - 1)
                right_sum = (total_sum - prefix_sum - idx) - idx * (size - i - 1)
                
                result[idx] = left_sum + right_sum
                prefix_sum += idx
        
        return result

public class Solution {
    public long[] GetDistances(int[] arr) {
        int n = arr.Length;
        long[] result = new long[n];
        Dictionary<int, List<int>> groups = new Dictionary<int, List<int>>();
        
        // 按值分组，记录每个值的所有下标
        for (int i = 0; i < n; i++) {
            if (!groups.ContainsKey(arr[i])) {
                groups[arr[i]] = new List<int>();
            }
            groups[arr[i]].Add(i);
        }
        
        // 对每组相同值的元素计算距离和
        foreach (var kvp in groups) {
            List<int> indices = kvp.Value;
            int size = indices.Count;
            if (size == 1) continue;
            
            // 计算总和和前缀和
            long totalSum = 0;
            foreach (int idx in indices) {
                totalSum += idx;
            }
            
            long prefixSum = 0;
            for (int i = 0; i < size; i++) {
                int idx = indices[i];
                // 左边的贡献
                long leftSum = (long)idx * i - prefixSum;
                // 右边的贡献
                long rightSum = (totalSum - prefixSum - idx) - (long)idx * (size - i - 1);
                
                result[idx] = leftSum + rightSum;
                prefixSum += idx;
            }
        }
        
        return result;
    }
}

var getDistances = function(arr) {
    const n = arr.length;
    const result = new Array(n).fill(0);
    const groups = new Map();
    
    // Group indices by value
    for (let i = 0; i < n; i++) {
        if (!groups.has(arr[i])) {
            groups.set(arr[i], []);
        }
        groups.get(arr[i]).push(i);
    }
    
    // For each group, calculate distances efficiently
    for (const indices of groups.values()) {
        const m = indices.length;
        if (m === 1) continue;
        
        // Calculate prefix sums for efficient distance calculation
        let leftSum = 0;
        let rightSum = 0;
        
        // Calculate total sum of all indices
        for (let i = 0; i < m; i++) {
            rightSum += indices[i];
        }
        
        for (let i = 0; i < m; i++) {
            const currentIndex = indices[i];
            rightSum -= currentIndex;
            
            // Sum of distances = (current * leftCount - leftSum) + (rightSum - current * rightCount)
            result[currentIndex] = (currentIndex * i - leftSum) + (rightSum - currentIndex * (m - i - 1));
            
            leftSum += currentIndex;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个元素只被处理一次
空间复杂度O(n) - 哈希表存储分组信息

相关题目