Degree of an Array

update May 14,2018 19:59

LeetCode

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.

Basic Idea:

先统计每个数字出现的次数，然后取出所有出现次数最多的数字，再从中找 first index 和 last index 距离最近的数字，返回 lastIndex - firstIndex + 1。

利用map分别统计每个数字出现次数以及首末index。

• C++ Code:

    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) {
            unordered_map<int, int> _countMap; // 存储数量
            unordered_map<int, int> _firstMap; // 存储第一次出现的index
            unordered_map<int, int> _lastMap;  // 存储最后一次出现的index
            for (int i = 0; i < nums.size(); ++i) {
                if (! _firstMap.count(nums[i])) _firstMap[nums[i]] = i;
            }
            for (int i = nums.size() - 1; i >= 0; --i) {
                if (! _lastMap.count(nums[i])) _lastMap[nums[i]] = i;
            }
  
            for (int num : nums) ++_countMap[num];
            vector<int> maxNums;
            int maxCount = 0;
            for (auto pair : _countMap) {
                if (pair.second > maxCount) {
                    maxCount = pair.second;
                    maxNums.clear();
                    maxNums.push_back(pair.first);
                } else if (pair.second == maxCount) {
                    maxNums.push_back(pair.first);
                }
            }
            int minLen = nums.size();
            for (int num : maxNums) {
                minLen = min(minLen, _lastMap[num] - _firstMap[num] + 1);
            }
            return minLen;
        }
    };