相同元素的间隔之和

难度: Medium

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

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

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

注意：|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⁵
1 <= arr[i] <= 10⁵

Submission

运行时间: 412 ms

内存: 50.8 MB

class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        index_mapping = defaultdict(list)
        result = [0] * len(arr)
        for i, a in enumerate(arr):
            index_mapping[a].append(i)
        for a in index_mapping:
            tmp_list = index_mapping[a]
            # print(tmp_list)
            if len(tmp_list) == 1:
                continue
            sum_val = sum(tmp_list)
            first = tmp_list[0]
            acc = first
            x = sum_val - len(tmp_list) * first
            # print(f"x: {x}")
            result[first] = x
            for i in range(1, len(tmp_list)):
                acc += tmp_list[i]
                # print(f"acc: {acc}")
                y = sum_val - 2 * acc + (i + 1) * tmp_list[i] - (len(tmp_list) - 1 - i) * tmp_list[i]
                # print(f"y: {y}")
                result[tmp_list[i]] = y
        return result

Explain

这个题解使用了一个哈希表（通过defaultdict实现）来记录每个元素在数组中出现的所有下标。对于数组中的每个不同元素，我们计算每个实例与其余相同元素的下标差的绝对值之和。为了高效地计算每个元素到其相同元素的间隔之和，算法首先计算所有下标的和（sum_val）。然后，对每个元素位置，使用前缀和（acc）来帮助计算距离之和。这种方法避免了对于每个元素重复计算总和，从而提高了效率。

时间复杂度: O(n)

空间复杂度: O(n)


class Solution:
    def getDistances(self, arr: List[int]) -> List[int]:
        index_mapping = defaultdict(list)  # 创建一个字典，用于存储每个元素的所有索引
        result = [0] * len(arr)  # 结果数组，初始化为0
        for i, a in enumerate(arr):  # 遍历数组，填充index_mapping
            index_mapping[a].append(i)
        for a in index_mapping:  # 对于每个不同的元素
            tmp_list = index_mapping[a]  # 获取该元素的所有索引
            if len(tmp_list) == 1:  # 如果该元素只出现一次，跳过
                continue
            sum_val = sum(tmp_list)  # 计算所有索引的和
            first = tmp_list[0]  # 第一个索引
            acc = first  # 前缀和的初始值
            x = sum_val - len(tmp_list) * first  # 计算第一个索引位置的间隔之和
            result[first] = x  # 更新结果数组
            for i in range(1, len(tmp_list)):  # 遍历剩下的索引
                acc += tmp_list[i]  # 更新前缀和
                y = sum_val - 2 * acc + (i + 1) * tmp_list[i] - (len(tmp_list) - 1 - i) * tmp_list[i]  # 计算当前索引的间隔之和
                result[tmp_list[i]] = y  # 更新结果数组
        return result

Explore

计算所有索引的和(sum_val)允许对于数组中的任何特定元素，快速获得与其他所有相同元素的索引之和。借助这个总和，对于每个索引，可以通过简单的减法操作来计算其与其他所有索引的距离总和，而无需逐一计算每个距离。前缀和(acc)用于追踪当前索引之前的所有相同元素的索引和，这样可以在常数时间内更新距离之和，而不是重新计算，从而提高效率。

在计算过程中，前缀和(acc)用于持续追踪到当前索引为止的所有相同元素索引的总和。对于每一个新的索引位置，通过更新前缀和（即加上当前索引值），并结合已知的所有索引之和(sum_val)，可以有效地计算出该索引与其余所有相同元素索引的距离之和。具体来说，每次计算中，使用累积的前缀和更新结果，加上或减去必要的值来快速得到当前索引的间隔之和，从而避免了对每个单独的索引重复进行全部距离的计算。

对于只出现一次的元素，其间隔之和自然为0，因为没有其他相同的元素与之计算距离。由于结果数组在开始时已被初始化为0，因此对于这些只出现一次的元素，跳过处理并不会影响结果数组中的值，这是一种有效的处理方式，可以减少不必要的计算。

这个公式是基于距离之和的数学推导得出的。其中`sum_val`是所有相同元素索引的总和，`2 * acc`是当前索引之前的所有索引的两倍之和（因为需要从sum_val中减去两次这部分以计算与后面索引的距离），`(i + 1) * tmp_list[i]`是考虑到当前索引之前的每个索引与当前索引的距离（共i+1个），而`(len(tmp_list) - 1 - i) * tmp_list[i]`则是当前索引与其后每个索引的距离的总和。将这些组合起来，可以直接计算出当前索引与数组中所有相同元素索引的距离之和。