LeetCode697. Degree of an Array解答

本是古典何须时尚 2022-06-07 09:08 157阅读 0赞

一早上起来，先做一道题降降起床气，这道题花了一个小时多十分钟，但是！当我看到accept之后的结果了的时候！  
![这里写图片描述][SouthEast]  
贼开心  
\#老规矩，先看一下题目

> 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;i<nums.length+1;i++){
                if(pos[nums[i-1]]!=0){
                    frequency[nums[i-1]]++;
                    currlength=i-pos[nums[i-1]]+1;
                    if(frequency[nums[i-1]]>maxfrequency){
                        maxfrequency=frequency[nums[i-1]];
                            minlength=currlength;
                    }else if(frequency[nums[i-1]]==maxfrequency){
                        minlength=currlength<minlength?currlength:minlength;
                    }
                }else{
                    pos[nums[i-1]]=i;
                }
            }
            if(maxfrequency==0){
                return 1;
            }
           return minlength;
        }
    }

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

[SouthEast]: /images/20220607/7fa5fd8d59db4455bf99890a097d2996.png