Skip to content

Latest commit

 

History

History
134 lines (88 loc) · 5.39 KB

5965.intervals-between-identical-elements.md

File metadata and controls

134 lines (88 loc) · 5.39 KB
Raw

题目地址(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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。