给定一个非空且只包含非负数的整数数组 nums,数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。
输入:nums = [1,2,2,3,1] 输出:2 解释: 输入数组的度是 2 ,因为元素 1 和 2 的出现频数最大,均为 2 。 连续子数组里面拥有相同度的有如下所示: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组 [2, 2] 的长度为 2 ,所以返回 2 。
输入:nums = [1,2,2,3,1,4,2] 输出:6 解释: 数组的度是 3 ,因为元素 2 重复出现 3 次。 所以 [2,2,3,1,4,2] 是最短子数组,因此返回 6 。
这种题感觉还挺好写的,首先用 reduce 来计算所有数字的频度, 然后找到最大数字的频度,直接通过在数组中找到该数字的 lastIndexOf - indexOf 就是最短连续子数组的长度了,时间复杂度就是 O(n)
如果有多个数字出现的频次一样,就需要使用 for 循环了, 然后在 for 循环里面还要使用 indexOf/lastIndexOf , 复杂度可能就是 O(n^2) 了
const findShortestSubArray = function (nums) {
// 算出所有数字出现的频次
let calc = nums.reduce((memo, current) => {
memo[current] ? memo[current]++ : (memo[current] = 1);
return memo;
}, {});
// 计算一下出现最多的频次数是多少
let keys = Object.keys(calc);
let max = 0; // 用来比较的
for (const key of keys) {
if (calc[key] >= max) {
max = calc[key];
}
}
// 把出现频次最多的数字添加到一个数组里面去
let arr = []; // 记录出现频次最多的数
for (const key of keys) {
if (calc[key] === max) {
arr.push(key);
}
}
// 从上面的那个数组中来计算最小的连续子数组
let res = Infinity;
for (const item of arr) {
// 因为在第一部计算所有数字的频次是加入到一个对象中,而对象的减值会转换成字符串,所以这里使用+来转换回来
let len = nums.lastIndexOf(+item) - nums.indexOf(+item);
if (len < res) {
res = len;
}
}
// 因为是连续子数组的长度,而 lastIndexOf - indexOf 是索引的差值,所以还要加上 1
return res + 1;
};
let nums = [4, 5, 1, 2, 2, 3, 1];
let result = findShortestSubArray(nums);
console.log(result);
优化优化,就是在第一次遍历的时候,就存储当前字段的次数,indexOf 和 lastIndexOf,这样的话,就只需要两次循环就可以了
const findShortestSubArray = function (nums) {
const mp = {};
for (const [i, num] of nums.entries()) {
if (num in mp) {
mp[num][0]++;
mp[num][2] = i;
} else {
// 第一个值是出现的次数,第二个值出现的是首次出现的位置,第三个值是最后一次出现的位置
mp[num] = [1, i, i];
}
}
let maxNum = 0,
minLen = 0;
for (const [count, left, right] of Object.values(mp)) {
if (maxNum < count) {
maxNum = count;
minLen = right - left + 1;
} else if (maxNum === count) {
if (minLen > right - left + 1) {
minLen = right - left + 1;
}
}
}
};
let nums = [];
let result = findShortestSubArray(nums);
console.log(result);