首页 > 其他分享 >【LeeCode】697. 数组的度

【LeeCode】697. 数组的度

时间:2022-12-18 17:31:25浏览次数:66  
标签:map 697 nums int get list LeeCode 数组 new

【题目描述】

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

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

​https://leetcode.cn/problems/degree-of-an-array/description/​


【示例】

【LeeCode】697. 数组的度_List

【代码】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<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;
}

标签:map,697,nums,int,get,list,LeeCode,数组,new
From: https://blog.51cto.com/u_13682316/5950931

相关文章

  • 链表与数组的区别
    原文链接:https://baijiahao.baidu.com/s?id=1743478279629141019物理存储结构不同链表与数组在计算机中存储元素采用不同的物理存储结构,数组是顺序存储结构,链表是链式......
  • 稀疏数组
    分析问题因为二维数组的很多默认值是0,因此记录了很多没有意义的数据解决:稀疏数组(记录有效的坐标)稀疏数组介绍1使用条件:当一个数组中大部分元素为0,或者为同一值的数组......
  • 简单认识指针数组与数组指针
    指针数组:指针数组就是一个存放指针的数组。//指针数组#include<stdio.h>intmain(){inta[5]={1,2,3,4,5};intb[]={2,3,4,5,6};intc[]=......
  • 【LeeCode】4. 寻找两个正序数组的中位数
    【题目描述】给定两个大小分别为 ​​m​​​ 和 ​​n​​​ 的正序(从小到大)数组 ​​nums1​​​ 和 ​​nums2​​。请你找出并返回这两个正序数组的 中位数 。......
  • 1764. 通过连接另一个数组的子数组得到一个数组
    1764.通过连接另一个数组的子数组得到一个数组题解:数据范围小,直接暴力双指针publicbooleancanChoose(int[][]groups,int[]nums){intn=groups.le......
  • 「双指针/kmp」通过连接另一个数组的子数组得到一个数组(力扣第1764题)
    本题为12月17日力扣每日一题题目来源:力扣第1764题题目tag:双指针kmp题面题目描述给你一个长度为n的二维整数数组groups,同时给你一个整数数组nums。你是否可以从n......
  • 力扣每日一题2022.12.17---1764. 通过连接另一个数组的子数组得到一个数组
    给你一个长度为n 的二维整数数组 groups ,同时给你一个整数数组 nums 。你是否可以从nums 中选出n 个不相交的子数组,使得第i 个子数组与groups[i] (下标从0......
  • 数组或者集合的选择
    想展示菜单,先找一个容器把所有的菜存起来,用户查看的时候直接展示。集合数组都是容器,但是数组的长度不好变化,集合更方便。定义集合表示饭店拥有的菜品。循环输出集合元素点的......
  • 【LeeCode】17. 电话号码的字母组合
    【题目描述】给定一个仅包含数字 ​​2-9​​ 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对......
  • 前端开发系列115-进阶篇之对象和数组的读写劫持
    title:前端开发系列115-进阶篇之对象和数组的读写劫持tags:categories:[]date:2019-04-0523:00:08本文讨论如何监听对象中所有属性的读和写操作,以及对于数组的劫......