697. Degree of an Array
1. Description
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.
2. Example
Example 1:
Input: nums = [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: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation:
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.
3. Note
- nums.length will be between 1 and 50,000.
- nums[i] will be an integer between 0 and 49,999.
4. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// int findShortestSubArray(vector<int>& nums)
int findShortestSubArray(vector<int> &i_nums)
{
int maxTimes = 0;
unordered_map<int, pair<int, pair<int, int>>> numTimesAndRange;
for(int i = 0; i < i_nums.size(); i++)
{
numTimesAndRange[i_nums[i]].first++;
maxTimes = max(maxTimes, numTimesAndRange[i_nums[i]].first);
if(numTimesAndRange[i_nums[i]].second.first == 0 && i_nums[i] != i_nums[0]) numTimesAndRange[i_nums[i]].second.first = i;
numTimesAndRange[i_nums[i]].second.second = i;
}
int result = INT_MAX;
for(auto iter : numTimesAndRange)
{
if(iter.second.first == maxTimes)
{
result = min(result, iter.second.second.second - iter.second.second.first + 1);
}
}
return result;
}
};