697. 数组的度(简单)

Posted on In Views:

1，问题描述

697. 数组的度

难度：简单

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

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

示例 1：

1
2
3
4
5
6
7
输入：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：

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

提示：

  • nums.length 在 1 到 50,000 范围内。
  • nums[i] 是一个在 0 到 49,999 范围内的整数。

2，初步思考

​ 问题拆分：

1️⃣找出数字出现次数最多的是那几个

2️⃣这几个数字，最左到最右的区间长度最短是多少！

​ 限制条件：

1️⃣长度最大为5w，可能有时间复杂度要求，那么就要想到空间换时间

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _697数组的度 {

    // 更快的解法：遍历数组两次
    public int findShortestSubArray_fast(int[] nums) {
        // 找出一遍遍历最大、最小值
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 设置缓存数据
        int[][] map = new int[max - min + 1][];
        int minLength = 1, maxDegree = 1;
        for (int i = 0; i < nums.length; i++) {
            int idx = nums[i] - min;
            int[] ints = map[idx];
            if (ints == null) {// 第一次出现
                ints = new int[]{1, i, i};
            } else {
                ints[0]++;
                if (ints[0] < maxDegree) {// 继续出现，但不是最大度
                    ints[2] = i;
                } else if (ints[0] == maxDegree) {// 同为最大度
                    ints[2] = i;
                    minLength = Math.min(minLength, ints[2] - ints[1] + 1);
                } else if (ints[0] > maxDegree) {// 更新最大度
                    maxDegree = ints[0];
                    ints[2] = i;
                    minLength = ints[2] - ints[1] + 1;
                }
            }
            map[idx] = ints;
        }
        return minLength;
    }


    // 官方解法
    public int findShortestSubArray_gov(int[] nums) {
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();// 0 代表次数，1 代表第一次出现的位置，2 代表最后一次出现的位置
        int maxDegree = 1;
        int minLength = 1;
        for (int i = 0; i < nums.length; i++) {
            int[] node = map.getOrDefault(nums[i], new int[]{0, -1, -1});
            node[0]++;
            if (node[0] == 1) {// 第一次出现
                node[1] = i;
            } else if (node[0] < maxDegree) {// 继续出现，但不是最大度
                node[2] = i;
            } else if (node[0] == maxDegree) {// 同为最大度
                node[2] = i;
                minLength = Math.min(minLength, node[2] - node[1] + 1);
            } else if (node[0] > maxDegree) {// 更新最大度
                maxDegree = node[0];
                node[2] = i;
                minLength = node[2] - node[1] + 1;
            }
            map.put(nums[i], node);
        }
        return minLength;
    }

    // 我自己的解法
    public int findShortestSubArray(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> maxNumList = new ArrayList<>();
        int maxDegress = 0;// 用于缓存当前最大度的数值

        List<Integer> list;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            list = map.getOrDefault(num, new ArrayList<>());
            list.add(i);
            map.put(num, list);// 处理list列表
            if (maxDegress < list.size()) {
                maxDegress = list.size();
                maxNumList = new ArrayList<>();
                maxNumList.add(num);
            } else if (maxDegress == list.size()) {
                maxNumList.add(num);
            }
        }// 检测maxDegree

        int minLength = Integer.MAX_VALUE;
        for (Integer num : maxNumList) {
            List<Integer> indexList = map.get(num);
            minLength = Math.min(minLength, indexList.getLast() - indexList.getFirst() + 1);
        }// 检测minLength
        return minLength;
    }

    public static void main(String[] args) {
        _697数组的度 degree = new _697数组的度();
//        System.out.println(degree.findShortestSubArray_gov(new int[]{1, 2, 2, 3, 1}));
        System.out.println(degree.findShortestSubArray_fast(new int[]{1, 2, 2, 3, 1, 4, 2}));
    }
}