LeetCode697. Degree of an Array解答

一早上起来，先做一道题降降起床气，这道题花了一个小时多十分钟，但是！当我看到accept之后的结果了的时候！

贼开心

#老规矩，先看一下题目

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.

题目大意是：在一个非空非负的int型数组中，定义degree为一个数组中的元素出现频率最大值。你的任务就是要寻找这个数组中出现频率最大的元素的最小距离（题目有点绕，多读几遍）

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.

解题思路

这个题目一看就不是什么好做的题目，既要频率最大，又要距离最小，这就是在搞事情。 经验告诉我，这种题目要是能只遍历一遍肯定是最好的算法，并且经验还告诉我，如果想要时间复杂度降低，那只有牺牲空间复杂度了，所以我需要额外的空间。 我想的是，维护一个int数组pos来保存它的每个元素在原始数组的位置，全部初始化为0。再维护一个int数组frequency保存它们出现的频率，用一个int变量标记最小长度，初始化为50000。遍历原始数组将每个元素映射到pos数组中，如果不是第一次出现，则计算第一次出现的位置与当前的位置的差，再查看frequency数组的该元素的频率，如果为最高则比较当前距离和全局最小距离取较小值。代码如下：

class Solution {
    public int findShortestSubArray(int[] nums) {
        int minlength=50000;
        int currlength;
        int maxfrequency=0;
        int[] frequency=new int[50001];
        int[] pos=new int[50001];
        
        if(nums.length==1){
            return 1;
        }
        for(int i=1;imaxfrequency){
                    maxfrequency=frequency[nums[i-1]];
                        minlength=currlength;
                }else if(frequency[nums[i-1]]==maxfrequency){
                    minlength=currlength

更好的算法

没有找到效率更高写法更简洁的算法了