解题过程
:::info
题目链接
集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。
:::
/**
* @link https://leetcode.cn/problems/degree-of-an-array/
* @title 697. 数组的度
* @description 给定一个非空且只包含非负数的整数数组 nums,数组的 度 的定义是指数组里任一元素出现频数的最大值。
* 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度
* @param {number[]} nums
* @return {number}
*/
// 解法一:
// 第一步:循环遍历数组每一项值,map记录数组元素出现的频次(默认为1,存在则累加),并记录累积最大值的数值
// 第二步:循环遍历数组索引,用一个变量记录最大值的数值
// 第三步:循环遍历数组索引,判断数组元素与最大值变量是否相等(可能出现过个数组元素出现数组的度一样情况)
// 第四步:找到当前数组元素在该数组出现的最后一次索引位置与当前首次出现索引位置的索引是否相同
// 第五步:不相同则设置统计变量记录当前数组元素已经统计过,计算数组元素当前索引位置与最后一次索引位置只差(最短连续子数组的长度)
// 第六步:计算最短连续子数组的长度的数组值由大到小排序,第一个就是最短连续子数组长度,且为空则默认设置长度为1,因为只有一个数组元素的情况下
var findShortestSubArray = function (nums) {
const elementCount = new Map() // 记录数组元素出现的频次
let maxNum = 0 // 最大数组元素频次的值
const res = [] // 记录数组的度元素的连续子数组长度的统计值
const sign = {} // 记录是否统计过数组元素最大频次统计值,包括最大频次有多个元素情况下
for (const value of nums) {
if (elementCount.has(value)) {
elementCount.set(value, elementCount.get(value) + 1)
} else {
elementCount.set(value, 1)
}
}
for (let i = 0; i < nums.length; i++) {
maxNum = Math.max(elementCount.get(nums[i]), maxNum)
}
for (let i = 0; i < nums.length; i++) {
if (elementCount.get(nums[i]) === maxNum) {
// 数组的度
const lastIndex = nums.lastIndexOf(nums[i])
if (!sign[nums[i]] && i !== lastIndex) {
sign[nums[i]] = true
// 记录当前元素值最后一个元素出现位置跟第一个元素出现位置的索引差
res.push(lastIndex - i + 1)
}
}
}
// 有小到大排序,为空则最小值是1(只有一个数组元素情况下)
return res.sort((a, b) => a - b)[0] || 1
}
// const result = findShortestSubArray([1, 2, 2, 3, 1]) // 2
// const result = findShortestSubArray([1, 2, 2, 3, 1, 4, 2]) // 6
const result = findShortestSubArray([1]) // 1
console.log(result)
解题感受
没有任何算法基础的考虑,不过这个时候我也不是很熟悉,就是常用的遇到问题怎么解决的思路,针对以前的教训,重点放在题干信息的截取上,专门拿了草稿纸写下题干重点,好处就是更专注审题了,解题思路果然效率高了很多,至少解法是针对自己记录的信息方向去想去写的代码,非常值得这样推荐做法,虽然可能会有点浪费时间,但是真的值得,对一道题的思考更深入和专注了