题目大意：求”度”相同的最短子数组的长度。
Problem:
https://leetcode.com/problems/degree-of-an-array/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.
Example 1:
|
1 2 3 4 5 6 7 |
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:
|
1 2 |
Input: [1,2,2,3,1,4,2] Output: 6 |
Solution 1: Hashtable
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 33 ms (beats 90.96%) class Solution { public: int findShortestSubArray(vector<int>& nums) { unordered_map<int, vector<int>> indices; for (int i = 0; i < nums.size(); ++i) indices[nums[i]].push_back(i); size_t degree = 0; for (const auto& p : indices) degree = max(degree, p.second.size()); int ans = nums.size(); for (const auto& p : indices) { if (p.second.size() != degree) continue; ans = min(ans, p.second.back() - p.second.front() + 1); } return ans; } }; |