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:
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.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
cnt = Counter(nums)
degree = cnt.most_common()[0][1]
left, right = {}, {}
for i, v in enumerate(nums):
if v not in left:
left[v] = i
right[v] = i
ans = inf
for v in nums:
if cnt[v] == degree:
t = right[v] - left[v] + 1
if ans > t:
ans = t
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
Map<Integer, Integer> left = new HashMap<>();
Map<Integer, Integer> right = new HashMap<>();
int degree = 0;
for (int i = 0; i < nums.length; ++i) {
int v = nums[i];
cnt.put(v, cnt.getOrDefault(v, 0) + 1);
degree = Math.max(degree, cnt.get(v));
if (!left.containsKey(v)) {
left.put(v, i);
}
right.put(v, i);
}
int ans = 1000000;
for (int v : nums) {
if (cnt.get(v) == degree) {
int t = right.get(v) - left.get(v) + 1;
if (ans > t) {
ans = t;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
unordered_map<int, int> cnt;
unordered_map<int, int> left;
unordered_map<int, int> right;
int degree = 0;
for (int i = 0; i < nums.size(); ++i) {
int v = nums[i];
degree = max(degree, ++cnt[v]);
if (!left.count(v)) {
left[v] = i;
}
right[v] = i;
}
int ans = 1e6;
for (int v : nums) {
if (cnt[v] == degree) {
int t = right[v] - left[v] + 1;
if (ans > t) {
ans = t;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func findShortestSubArray(nums []int) int {
cnt := map[int]int{}
left := map[int]int{}
right := map[int]int{}
var degree int
for i, v := range nums {
cnt[v]++
if degree < cnt[v] {
degree = cnt[v]
}
if _, ok := left[v]; !ok {
left[v] = i
}
right[v] = i
}
ans := 100000
for v, c := range cnt {
if c == degree {
t := right[v] - left[v] + 1
if ans > t {
ans = t
}
}
}
return ans
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| func findShortestSubArray(nums []int) (ans int) {
ans = 50000
numsMap := make(map[int]int, len(nums))
for _, num := range nums {
numsMap[num]++
}
var maxDegree int
for _, num := range numsMap {
maxDegree = max(num, maxDegree)
}
degreeNums := getMaxDegreeElem(maxDegree, numsMap)
for _, num := range degreeNums {
f := findSubArray(num, nums)
ans = min(ans, f)
}
return
}
func findSubArray(target int, nums []int) int {
start := getStartIdx(target, nums)
end := getEndIdx(target, nums)
return (end - start) + 1
}
func getStartIdx(target int, nums []int) (start int) {
for idx, num := range nums {
if num == target {
start = idx
break
}
}
return start
}
func getEndIdx(target int, nums []int) (end int) {
for i := len(nums) - 1; i > 0; i-- {
if nums[i] == target {
end = i
break
}
}
return
}
func getMaxDegreeElem(maxDegree int, numsMap map[int]int) []int {
var ans []int
for key, value := range numsMap {
if value == maxDegree {
ans = append(ans, key)
}
}
return ans
}
|
