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]>

 1 class Solution 
 2 {
 3     public int findShortestSubArray(int[] nums) 
 4     {
 5         HashMap<Integer, int[]> map = new HashMap<>();
 6         int maxFre = 0;
 7         int minLen = Integer.MAX_VALUE;
 8         
 9         // first nums iteration: store first index, last index, occurrence and find out the maxFre
10         for(int i=0; i<nums.length; i++) 
11         {
12             if(map.containsKey(nums[i])) // num is already in map
13             {
14                 map.get(nums[i])[1] = i; // update this num's end index
15                 map.get(nums[i])[2]++;   // update this num's occurrence  
16             }
17             else // first time that store into map
18             {
19                 int[] numInfo = new int[3];
20                 numInfo[0] = i; // store this num's begin index
21                 numInfo[1] = i; // store this num's end index
22                 numInfo[2] = 1; // store this num's occurrence
23                 map.put(nums[i], numInfo);
24             }
25             
26             maxFre = Math.max(maxFre, map.get(nums[i])[2]); // update maxFre
27         }
28         
29         // second map keys iteration: find the minLen for numbers that have maxFre
30         for(int num: map.keySet())
31             if(maxFre == map.get(num)[2])
32                 minLen = Math.min(minLen, map.get(num)[1] - map.get(num)[0] + 1);
33 
34         
35         return minLen;
36     }
37 }

参考资料:N/A

LeetCode 题目列表 - LeetCode Questions List

原文地址:https://www.cnblogs.com/jimmycheng/p/7726927.html