LeetCode 697. Degree of an Array （数组的度）

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.

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.

 

---

 

题目标签：Array

　　题目给了我们一个 nums array， 让我们首先找到 出现最多次数的数字（可能多于1个），然后在这些数字中，找到一个 长度最小的 数字。返回它的长度。

　　比较直接的想法就是，既然我们首先要知道每一个数字出现的次数，那么就利用HashMap，而且我们还要知道 这个数字的最小index 和最大index，那么也可以存入map记录。

　　设一个HashMap<Integer, int[]> map， key 就是 num，value 就是int[3]: int[0] 记录 firstIndex; int[1] 记录 lastIndex; int[2] 记录次数。

　　这样的话，我们需要遍历两次：

　　　　第一次遍历nums array：记录每一个数字的 firstIndex， lastIndex， 出现次数； 还要记录下最大的出现次数。

　　　　第二次遍历map key set：当key (num) 的次数等于最大次数的时候，记录最小的长度。(lastIndex - firstIndex + 1)。

 

 

Java Solution:

Runtime beats 74.35% 

完成日期：10/24/2017

关键词：Array

关键点：HashMap<num, [firstIndex, lastIndex, Occurrence]>

class Solution 
{
    public int findShortestSubArray(int[] nums) 
    {
        HashMap<Integer, int[]> map = new HashMap<>();
        int maxFre = 0;
        int minLen = Integer.MAX_VALUE;
        
        // first nums iteration: store first index, last index, occurrence and find out the maxFre
        for(int i=0; i<nums.length; i++) 
        {
            if(map.containsKey(nums[i])) // num is already in map
            {
                map.get(nums[i])[1] = i; // update this num's end index
                map.get(nums[i])[2]++;   // update this num's occurrence  
            }
            else // first time that store into map
            {
                int[] numInfo = new int[3];
                numInfo[0] = i; // store this num's begin index
                numInfo[1] = i; // store this num's end index
                numInfo[2] = 1; // store this num's occurrence
                map.put(nums[i], numInfo);
            }
            
            maxFre = Math.max(maxFre, map.get(nums[i])[2]); // update maxFre
        }
        
        // second map keys iteration: find the minLen for numbers that have maxFre
        for(int num: map.keySet())
            if(maxFre == map.get(num)[2])
                minLen = Math.min(minLen, map.get(num)[1] - map.get(num)[0] + 1);

        
        return minLen;
    }
}

参考资料：N/A

 

LeetCode 题目列表 - LeetCode Questions List