LeetCode Degree of an Array
2024-09-04 16:47:53
原题链接在这里:https://leetcode.com/problems/degree-of-an-array/description/
题目:
Given a non-empty array of non-negative integers nums
, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of nums
, that has the same degree as nums
.
Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6
Note:
nums.length
will be between 1 and 50,000.nums[i]
will be an integer between 0 and 49,999.
题解:
找出最大的frequency, 并标注对应的element出现过的左右index位置.
Time Complexity: O(n). n = nums.length.
Space: O(n).
AC Java:
class Solution {
public int findShortestSubArray(int[] nums) {
HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> leftInd = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> rightInd = new HashMap<Integer, Integer>();
int degree = 0; for(int i = 0; i<nums.length; i++){
count.put(nums[i], count.getOrDefault(nums[i], 0)+1);
degree = Math.max(degree, count.get(nums[i])); if(leftInd.get(nums[i]) == null){
leftInd.put(nums[i], i);
}
rightInd.put(nums[i], i);
} int res = Integer.MAX_VALUE;
for(int i = 0; i<nums.length; i++){
if(count.get(nums[i]) == degree){
res = Math.min(res, rightInd.get(nums[i]) - leftInd.get(nums[i]) + 1);
}
} return res;
}
}
最新文章
- 新手学习web遇到的一些乱码问题
- C#/VB.NET Excel数据分列
- HTTPf服务器(3)
- markdown语法说明
- DBUtils
- 使用ISO文件安装Linux
- [asp.net mvc]自定义filter
- [转] What is Ec/Io (and Eb/No)?
- fstab 介绍
- VirtualBox安装linux增强工具报错
- 九、cocos2dx之Actions
- 使用hadoop命令rcc生成Record 一个简单的方法来实现自己的定义writable对象
- 【Codeforces 837D】Round Subset
- EffectiveC++笔记 目录
- B/S架构
- Django积木块五——分页
- (转载)intellj idea 如何设置类头注释和方法注释
- Neural Networks and Deep Learning 课程笔记(第四周)深层神经网络(Deep Neural Networks)
- Python实现进度条功能
- ios UrlEncode与UrlDecode
热门文章
- Linux 设置中文编码
- linux 配置tensorflow 全过程记录
- HTML5/CSS3实现图片倒影效果
- 【转】React Native中ES5 ES6写法对照
- JSP Tomcat8.0运行连接池时发生异常【AbstractMethodError oracle.jdbc.driver.T4CConnection.isValid(I)Z】
- React之JSX语法
- 【I/O】常见输入输出
- [Ctsc2000]冰原探险
- Java Swing窗体小工具实例 - 原创
- 使用ConcurrentLinkedQueue惨痛的教训