【LeeCode】697. 数组的度

【题目描述】

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