Array
Hash Table
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
Python3 Java C++ Go
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
Go
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
}
GitHub