第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
5965. 相同元素的间隔之和

题目地址(5965. 相同元素的间隔之和)

https://leetcode-cn.com/problems/intervals-between-identical-elements/

题目描述

给你一个下标从 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^5
1 <= arr[i] <= 10^5

前置知识

  • 前缀和

公司

  • 暂无

思路

朴素的思路是 $n^2$ 的暴力枚举,即对于每一个索引 i ,暴力枚举其与数组所有其他索引的间隔,并将其全部加起来即可。
考虑到数据范围为 $10^5$, 因此上面的思路是不可行的,会超时。我们的思路是优化到至少 $nlogn$。这种数据规模要么优化到 $nlogn$ 要么就是 $n$。
如果优化到 $n$。对于这种题目容易想到的就是动态规划,单调栈,前缀和。
首先想到的思路是动态规划。对于每一个索引 i ,我们是否可以借助其他索引的间隔和得到答案。
答案是可以的!这里的其他索引具体来说其实是其他的和 arr[i] 值相等的索引。 不难想到用 dp[i] 表示子数组 arr[:i] 中 i 的间隔和,最终答案就是 dp[n-1]。
这是一个最初的想法。实际上还有需要细节需要处理。
  • 首先, i 向前看的时候需要看的是和 arr[i] 值相同的已处理好的答案。因此我们的 dp 定义少了一个维度。不妨用 dp[i][x] 表示 子数组 arr[:i] 且值为的 x 的 i 的间隔和,最终答案就是对于数组所有 x dp[n-1][x] 求和。
  • 其次,如果计算间隔和呢?上面的朴素的思路是对于 i ,枚举所有小于 i 的 j,如果 arr[j] == arr[i], 则加入到间隔和。
  • 如果优化上一步的计算呢?我们可以利用类似前缀和的技巧来计算。 其中 pre[a] 表示上一次出现的 a 的间隔和。 那么 i 的间隔和就是 (i - last)*cnt + pre[last] ,其中 last 就是 a 的上一次出现的位置,cnt 是 i 的前面的 a 出现的次数。这提示我们除了维护前缀信息,也要维护 cnt 信息。 pre[a] = (v, c) 表示上一个 a 的位置的前缀间隔和为 v,且前面和 a 相同的数字有 c 个。
对于每一个 i 仅按照上面的计算会漏掉 i 右侧部分的间隔和。因此我们可以使用相同的技巧,用一个后缀和来解决。

关键点

  • 前缀和 + 后缀和优化时间复杂度

代码

  • 语言支持:Python3
Python3 Code:
class Solution:
def getDistances(self, arr: List[int]) -> List[int]:
ans = []
n = len(arr)
last_map = collections.defaultdict(lambda:-1)
pre = collections.defaultdict(lambda:(0,0))
suf = collections.defaultdict(lambda:(0,0))
for i in range(n):
a = arr[i]
last = last_map[a]
v, c = pre[last]
pre[i] = v + c * (i - last), c + 1
last_map[a] = i
last_map = collections.defaultdict(lambda:len(arr))
for i in range(n-1,-1,-1):
a = arr[i]
last = last_map[a]
v, c = suf[last]
suf[i] = v + c * (last - i), c + 1
last_map[a] = i
for i, a in enumerate(arr):
ans.append(pre[i][0] + suf[i][0])
return ans
复杂度分析
令 n 为数组长度。
  • 时间复杂度:我们遍历了两次数组,因此时间复杂度为 $O(n)$
  • 空间复杂度:pre 和 suf 以及 last_map 都和数组不同数字的个数同阶,最差情况数组都是不同的,此时空间复杂度为 $O(n)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。