【题目描述】
给定一个非空且只包含非负数的整数数组 nums
,数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums
中找到与 nums
拥有相同大小的度的最短连续子数组,返回其长度
https://leetcode.cn/problems/degree-of-an-array/description/
【示例】
【代码】admin
代码应该能用, 但测试用例通过 23 / 89 会因为超时而导致检测失败
import java.util.*;
// 2022-12-17
class Solution {
public int findShortestSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 统计数组中 各个数字出现的次数
Map<Integer,Integer> map = new HashMap<>();
// 用list来存储每个字符, 没有用StringBuilder是如果像 4999这种数字, 转字符串就变成4 9 9 9了
List<String> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
list.add(String.valueOf(nums[i]));
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
//Integer value = map.entrySet().stream().max(Map.Entry.comparingByValue()).get().getValue();
int val = map.values().stream().max(Comparator.naturalOrder()).get().intValue();
// 记录最小值
int min = Integer.MAX_VALUE;
// 记录所有的结果集
List<List<String>> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++){
// 从右向左依次缩减字符串的长度
int l = i;
int r = nums.length;
while (l < r){
// 获取中间状态的字符串
List<String> list2 = new ArrayList<>();
for (int j = l; j < r; j++){
list2.add(list.get(j));
}
// 检查是否符合 度的概念, 统计记录最小的
if (check(list2, val)){
min = Math.min(min, list2.size());
// 记录可能的结果集
res.add(list2);
}
// 每次左边的位置不动(随着外层循环自增), 缩小右侧的指针范围
r--;
}
}
// 打印所有的可能集
System.out.println(res);
System.out.println("MIN: " + min);
return min;
}
private boolean check(List<String> tmp, int val) {
boolean flag = false;
Map<String,Integer> map = new HashMap<>();
for (int i = 0; i < tmp.size(); i++) {
String c = tmp.get(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (Integer value : map.values()) {
if (value == val){
flag = true;
break;
}
}
return flag;
}
}
public class Main{
public static void main(String[] args) {
int[] arr = {1,2,2,3,1,4,2}; // 输出: 6
int[] arr1 = {1,2,2,3,1}; // 输出: 2
new Solution().findShortestSubArray(arr);
new Solution().findShortestSubArray(arr1);
int[] arr2 = {49999,1,1,1,2,1};
new Solution().findShortestSubArray(arr2); // 输出: 5
int[] arr3 = {49999,100,2,100,100,4,100};
new Solution().findShortestSubArray(arr3); // 输出: 6
}
}
【代码】大男孩
通过map的value来记录数组中元素出现的次数以及最后一次出现的下标
import java.util.*;
import java.util.regex.Pattern;
// 2022-12-16
class Solution {
public int findShortestSubArray(int[] nums) {
int len = nums.length;
if (nums.length == 0) return 0;
// key: nums[i]的值
// value: 数组, 记录出现的次数、起始、终止位置
Map<Integer, int[]> map = new HashMap<>();
for (int i = 0; i < len; i++){
if (map.containsKey(nums[i])){
map.get(nums[i])[0]++;
map.get(nums[i])[2] = i;
}else {
map.put(nums[i], new int[]{1, i, i});
}
}
int maxNum = 0;
int minLen = 0;
for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
int[] tmp = entry.getValue();
if (tmp[0] > maxNum){
maxNum = tmp[0];
minLen = tmp[2] - tmp[1] + 1;
}else if (tmp[0] == maxNum){
if (minLen > tmp[2] - tmp[1] + 1){
minLen = tmp[2] - tmp[1] + 1;
}
}
}
System.out.println(minLen);
return minLen;
}
}
public class Main{
public static void main(String[] args) {
int[] arr = {1,2,2,3,1,4,2}; // 输出: 6
int[] arr1 = {1,2,2,3,1}; // 输出: 2
new Solution().findShortestSubArray(arr);
new Solution().findShortestSubArray(arr1);
int[] arr2 = {49999,1,1,1,2,1};
new Solution().findShortestSubArray(arr2); // 输出: 5
int[] arr3 = {49999,100,2,100,100,4,100};
new Solution().findShortestSubArray(arr3); // 输出: 6
}
}
【代码】pumpkin
原理同上
public static int findShortestSubArray(int[] nums) {标签:map,697,nums,int,get,list,LeeCode,数组,new From: https://blog.51cto.com/u_13682316/5950931
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(i);
list.add(i);
map.put(nums[i], list);
} else {
List<Integer> list = map.get(nums[i]);
list.set(0, list.get(0) + 1);
list.set(2, i);
}
}
int ans = 0, du = 0;
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
List<Integer> value = entry.getValue();
Integer size = value.get(0);
if (size > du) {
du = size;
ans = value.get(2) - value.get(1) + 1;
}
if (size == du) {
ans = Math.min(ans, value.get(2) - value.get(1) + 1);
}
}
return ans;
}