[Leetcode] 0697.数组的度

news/2024/11/2 3:28:20/

697. 数组的度

点击上方标题跳转至leetcode

题目描述

给定一个非空且只包含非负数的整数数组 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 。

示例 2:

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

提示:

  • nums.length 在 150,000 范围内。
  • nums[i] 是一个在 049,999 范围内的整数。

解法

方法一:哈希表

遍历数组,用哈希表记录数组每个元素出现的次数,以及首次、末次出现的位置。然后遍历哈希表,获取元素出现次数最多(可能有多个)且首末位置差最小的数。

记原数组中出现次数最多的数为 x,那么和原数组的度相同的最短连续子数组,必然包含了原数组中的全部 x,且两端恰为 x 第一次出现和最后一次出现的位置。
因为符合条件的 x 可能有多个,即多个不同的数在原数组中出现次数相同。所以为了找到这个子数组,我们需要统计每一个数出现的次数,同时还需要统计每一个数第一次出现和最后一次出现的位置。

在实际代码中,我们使用哈希表实现该功能,每一个数映射到一个长度为 3 的数组,数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。当我们记录完所有信息后,我们需要遍历该哈希表,找到元素出现次数最多,且前后位置差最小的数。

时间复杂度 O(n),空间复杂度 O(n)。其中 n 为数组长度。

Python3

from typing import Listclass Solution:def findShortestSubArray(self, nums: List[int]) -> int:mp = dict()for i,num in enumerate(nums):if num in mp:mp[num][0] +=1mp[num][2] = ielse:mp[num] = [1,i,i]maxNum = minLen = 0for count, left, right in mp.values():span = right - left + 1if maxNum < count:maxNum = countminLen = spanelif maxNum == count:if minLen > span:minLen = spanreturn minLennums = [1,2,2,3,1]
fun = Solution()
res = fun.findShortestSubArray(nums)
print(res)
class Solution:def findShortestSubArray(self, nums: List[int]) -> int:cnt = Counter(nums)degree = cnt.most_common()[0][1]left, right = {}, {}for i, v in enumerate(nums):if v not in left:left[v] = iright[v] = ians = inffor v in nums:if cnt[v] == degree:t = right[v] - left[v] + 1if ans > t:ans = treturn ans

C++

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;class Solution{
public:int findShortestSubArray(vector<int>& nums) {unordered_map<int, vector<int> >mp;int n = nums.size();for(int i = 0; i < n; i++){if(mp.count(nums[i])){mp[nums[i]][0]++;mp[nums[i]][2] = i;}else{mp[nums[i]] = {1,i,i};}}int maxNum = 0,minLen = 0;for (unordered_map<int, vector<int>>::iterator i= mp.begin(); i!=mp.end();++i) {vector<int> vec = i-> second;// for (auto& [_, vec] : mp) {int span = vec[2] - vec[1] +1;if(maxNum < vec[0]){maxNum = vec[0];minLen = span;}else if (maxNum == vec[0]){if(minLen > span)minLen = span;}}return minLen;}
};int main(){vector<int> nums = {1,2,2,3,1};int res = Solution().findShortestSubArray(nums);cout << "res: " << res << endl;return 0;
}
//g++ 697.cpp -std=c++11
class Solution {
public:int findShortestSubArray(vector<int>& nums) {unordered_map<int, int> cnt;unordered_map<int, int> left;unordered_map<int, int> right;int degree = 0;for (int i = 0; i < nums.size(); ++i) {int v = nums[i];degree = max(degree, ++cnt[v]);if (!left.count(v)) {left[v] = i;}right[v] = i;}int ans = 1e6;for (int v : nums) {if (cnt[v] == degree) {int t = right[v] - left[v] + 1;if (ans > t) {ans = t;}}}return ans;}
};

http://www.ppmy.cn/news/59907.html

相关文章

【三十天精通Vue 3】第二十四天 Vue3 移动端适配和响应式布局

✅创作者:陈书予 🎉个人主页:陈书予的个人主页 🍁陈书予的个人社区,欢迎你的加入: 陈书予的社区 🌟专栏地址: 三十天精通 Vue 3 文章目录 引言一、 移动端适配概述1.1 为什么需要移动端适配?1.2 移动端适配方案比较1.3 常用的移动端适配方案二、 响应式布局概述2.1 …

【LocalMapping】

这段代码中,LocalMapping类是ORB_SLAM2算法中的局部地图构建模块。局部地图构建的任务包括处理新的关键帧、创建新的地图点、地图点筛选、关键帧筛选以及与相邻关键帧的地图点搜索。LocalMapping类在SLAM系统中与跟踪(Tracking)、闭环检测(LoopClosing)等其他模块共同工作…

【华为OD机试 2023最新 】箱子之字形摆放(C语言题解 100%)

文章目录 题目描述输入描述输出描述备注用例题目解析C语言题目描述 有一批箱子(形式为字符串,设为str), 要求将这批箱子按从上到下以之字形的顺序摆放在宽度为 n 的空地,请输出箱子的摆放位置。 例如:箱子ABCDEFG,空地宽度为3,摆放结果如图: 则输出结果为: AFG BE C…

网络钓鱼仍然是安全行业的祸害

随着网络犯罪分子采用更先进的方法&#xff0c;网络钓鱼诈骗继续构成重大风险。 根据 Zscaler 最新发布的 2023 ThreatLabz 网络钓鱼报告&#xff0c;随着网络钓鱼工具包和ChatGPT等人工智能 (AI) 工具的广泛使用&#xff0c;网络犯罪分子比以往任何时候都更容易创建有针对性的…

java的类加载浅析

类加载 类加载器 类加载器是Java虚拟机&#xff08;JVM&#xff09;的一个组成部分&#xff0c;它的主要任务是在运行时动态加载类和资源&#xff0c;以便程序能够使用它们。类加载器从文件系统、网络或其他来源中获取类的字节码&#xff0c;并将其转换为JVM可执行的形式&…

java入门-W6(K1-K26)集合初

1.Map集合 1.1Map集合概述和特点【理解】 Map集合概述 interface Map<K,V> K&#xff1a;键的类型&#xff1b;V&#xff1a;值的类型Map集合的特点 双列集合,一个键对应一个值键不可以重复,值可以重复 Map集合的基本使用 public class MapDemo01 {public static void…

金豺(GJO)优化算法、matlab代码实现以及与PSO、GWO、SO算法比对

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言1 算法原理2 算法步骤2.1 初始化种群2.2 搜索猎物(全局搜索)2.3 包围和围捕猎物&#xff08;局部搜索&#xff09;2.4 从全局搜索转向局部搜索 3 算法流程图4 m…

HCIA的OSPF理论与实验

第6章:OSPF 开放式最短路径优先(Open Shortest Path First,OSPF)是IETF组织开发的一个基于链路状态的内部网关协议(Interior Gateway Protocol)。目前针对IPv4协议使用的是OSPF Version 2(RFC2328);针对IPv6协议使用OSPF Version 3(RFC2740)。如无特殊说明,本章所…