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