专业的营销网站,渝中网站建设,青海移动端网页设计,网站升级改版方案文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。
arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地#xff0c;arr[i] 和 arr[j] 之间的间隔是 |i - j| 。
返回一个长度为 n 的数组 intervals #xff0c;其中 interva…
文章目录1. 题目2. 解题1. 题目
给你一个下标从 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/intervals-between-identical-elements 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
按照数字分组对每组数字的 下标求前缀和因为对 i 位置前面的可以拆成 i-i前后面的可以拆成 i后-i利用前缀和获取同符号的区间的和
class Solution {
public:vectorlong long getDistances(vectorint arr) {unordered_mapint,vectorlong long pos; // 相同数字的位置for(int i 0; i arr.size(); i)pos[arr[i]].push_back(i); // 数字的各个位置vectorlong long ans(arr.size(), 0);for(auto p : pos){vectorlong long pp p.second;for(int i 1; i pp.size(); i)pp[i] pp[i-1]; // 各个位置的前缀和int lnum 0, rnum p.second.size();for(int i 0; i p.second.size(); i){lnum i; // i 左边有的同数字的 个数rnum p.second.size()-i-1; // 右侧有的个数long long idx p.second[i]; // 对应原来数组中的位置ans[idx] pp.back()-pp[i] - idx*rnum idx*lnum - (i0 ? pp[i-1] : 0);// a1,a2,... i, ... b1, b2 后半段的都可以拆成 b1-i, b2-i, 个数 rnum个// 前半段 都可以拆成 i-a1, i-a2,... 个数 lnum个// a1, a2, ... 的和用前缀和直接获取// b1, b2, ... 的和用前缀和做差获取}}return ans;}
};340 ms 131.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
