刷爆力扣之数组的度

刷爆力扣之数组的度

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈

今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

697. 数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入：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 。
1
2
3
4
5
6
7

示例 2：

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
1
2
3
4
5

提示：

• nums.length 在 1 到 50,000 范围内。
• nums[i] 是一个在 0 到 49,999 范围内的整数。

二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎

① 数组的 度 定义是指数组里任一元素出现频数的最大值 = 记录每个元素个数即可 🌹🌹🌹

② 找到与 nums 拥有相同大小度的最短连续子数组，返回其长度 = 最大个数元素的最后索引位置减去第一次索引位置加一 🌸🌸🌸

提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃

2.2 🚀 思路整理

哈希表法

每一个数映射到一个长度为 3 的数组，数组的三个元素分别代表这个数出现的次数、原数组中第一次出现的位置和在原数组中最后出现的位置。记录完所有信息后，遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数 🌺🌺🌺

整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃

三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

int findShortestSubArray(vector& nums) {
    unordered_map> mp; //定义哈希表
    int n = nums.size(); //获取数组长度
    
    for (int i = 0; i < n; i++) { //遍历数组
        if (mp.count(nums[i])) { //如果 nums[i] 存在于哈希表
            mp[nums[i]][0]++; //将这个数出现次数加一
            mp[nums[i]][2] = i; //将这个数最后出现位置更新
        } else {
            mp[nums[i]] = {1, i, i}; //如果 nums[i] 不存在于哈希表, 则插入
        }
    }
    
    int maxNum = 0, minLen = 0; //定义最大频数和最短长度
    for (auto& [_, vec] : mp) { //遍历哈希表
        if (maxNum < vec[0]) { //若频数大于当前最大频数
            maxNum = vec[0]; //将最大频数更新
            minLen = vec[2] - vec[1] + 1; //将最短长度更新
        } else if (maxNum == vec[0]) { //频数等于当前最大频数
            if (minLen > vec[2] - vec[1] + 1) { //比较长度
                minLen = vec[2] - vec[1] + 1; //将最短长度更新
            }
        }
    }
    return minLen; //返回最短长度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

unordered_map> mp; //定义哈希表
1

解题没什么问题，但实际应用中哈希表和 Vector 嵌套会很影响性能（STL 容器的频繁创建和销毁十分耗时）

很直白的题，无特殊点，核心是 最大个数元素的最后索引位置减去第一次索引位置加一 🐳🐳🐳

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题

代码实现使用了两个哈希表，其键均为 KEY : nums[i] 😶😶😶 ，代码如下 👇👇👇👇

 int findShortestSubArray(vector& nums) {
        std::unordered_map> map1; //VAL : beginIndex, endIndex
        std::unordered_map map2; //VAL : count

        int len = nums.size(); //获取数组长度
        for (int i = 0; i < len; ++i) { //遍历数组
            if (map1.find(nums[i]) == map1.end()) {
                map1[nums[i]] = std::make_pair(i, i);
			    map2[nums[i]] = 1;
            } else {
                map1[nums[i]].second = i;
                ++map2[nums[i]];
            }
        }

        int maxCount = 0, shortestLen = INT_MAX;
        for (auto& elem : map2) {
            if (elem.second < maxCount) continue;
            else if (elem.second > maxCount) shortestLen = map1[elem.first].second - map1[elem.first].first + 1;
            else shortestLen = std::min(map1[elem.first].second - map1[elem.first].first + 1, shortestLen);

            maxCount = elem.second;
	    }

        return shortestLen;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪