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: 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.
Constraints:
nums.length
will be between 1 and 50,000.nums[i]
will be an integer between 0 and 49,999.
A:
用一个map 来计算出degree来, 再用左右 index runner来跟着计算刚达到的degree
class Solution { public: int findShortestSubArray(vector<int>& nums) { int degree = 0; unordered_map<int,int> map; // count of for(auto k : nums){ map[k] +=1; degree = max(degree, map[k]); } map.clear(); int res = nums.size(); int begin = 0; for(int end = 0;end<nums.size(); ++end) { int k = nums[end]; map[k] += 1; if(map[k] == degree) { //loop till not equal while(nums[begin] != k) { map[nums[begin]] -= 1; ++begin; } res = min(res, end-begin+1); ++begin; map[k] -= 1; } } return res; } };
No comments:
Post a Comment