6360. 等值距离和
早上打的时候只会用暴力,O(n方)超时
贴一下暴力代码:
/**
* @param {number[]} nums
* @return {number[]}
*/
var distance = function (nums) {
let map = new Map()
let ans = []
for (let i = 0; i < nums.length; i++) {
console.log(map);
if (map.has(nums[i])) {
let last = map.get(nums[i])
map.set(nums[i], [...last, i])
}
else {
map.set(nums[i], [i])
}
}
for (let i = 0; i < nums.length; i++) {
let val = map.get(nums[i])
let w = 0;
for (let j = 0; j < val.length; j++) {
if (val[j] === i) continue;
w += Math.abs(i - val[j]);
}
ans[i] = w;
}
return ans;
};
具体做法:
- 将数组中相同值的下标装进一个数组里
- 前缀和求出它与其它相同值的下标的距离
使用前缀和优化第二步
/**
* @param {number[]} nums
* @return {number[]}
*/
var distance = function (nums) {
let map = {};
let ans = [];
let len = nums.length;
for (let i = 0; i < len; i++) {
if(!map[nums[i]]) {
map[nums[i]] = [i];
} else {
map[nums[i]].push(i);
}
}
let s = [];
s[0] = 0;
for(let key in map) {
let value = map[key];
let n = value.length;
for(let i = 0 ; i < n ; i ++) {
s[i+1] = s[i] + value[i];
}
for(let i = 0 ; i < n ; i ++) {
let target = value[i];
let left = target * i - s[i];
let right = s[n] - s[i] - target * (n - i);
ans[target] = left + right;
}
}
return ans;
};
思路相同:
2602. 使数组元素全部相等的最少操作次数