A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
Topological Sort
Hash Table
599 Minimum Index Sum of Two Lists
697 Degree of an Array
734 Sentence Similarity
749 Shortest Completing Word
760 Find Anagram Mappings
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By
GitBook
697 Degree of an Array
697.
Degree of an Array
1. Question
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
Input: [1, 2, 2, 3, 1]
2
3
Output: 2
4
5
Explanation:
6
7
The input array has a degree of 2 because both elements 1 and 2 appear twice.
8
Of the subarrays that have the same degree:
9
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
10
The shortest length is 2. So return 2.
Copied!
Example 2:
1
Input: [1,2,2,3,1,4,2]
2
3
Output: 6
Copied!
Note:
nums.length
will be between 1 and 50,000.
nums[i]
will be an integer between 0 and 49,999.
2. Implementation
(1) Hash Table
1
class
Solution
{
2
public
int
findShortestSubArray
(
int
[]
nums
)
{
3
Map
<
Integer
,
int
[]
>
range
=
new
HashMap
<>
();
4
Map
<
Integer
,
Integer
>
count
=
new
HashMap
<>
();
5
6
int
maxFreq
=
0
;
7
8
for
(
int
i
=
0
;
i
<
nums
.
length
;
i
++
)
{
9
count
.
put
(
nums
[
i
],
count
.
getOrDefault
(
nums
[
i
],
0
)
+
1
);
10
maxFreq
=
Math
.
max
(
maxFreq
,
count
.
get
(
nums
[
i
]));
11
12
range
.
putIfAbsent
(
nums
[
i
],
new
int
[]
{
-
1
,
-
1
});
13
int
[]
temp
=
range
.
get
(
nums
[
i
]);
14
if
(
temp
[
0
]
==
-
1
)
{
15
temp
[
0
]
=
i
;
16
}
17
temp
[
1
]
=
i
;
18
}
19
20
int
minLen
=
nums
.
length
;
21
22
for
(
int
key
:
count
.
keySet
())
{
23
if
(
count
.
get
(
key
)
==
maxFreq
)
{
24
int
[]
temp
=
range
.
get
(
key
);
25
minLen
=
Math
.
min
(
minLen
,
temp
[
1
]
-
temp
[
0
]
+
1
);
26
}
27
}
28
return
minLen
;
29
}
30
}
Copied!
3. Time & Space Complexity
Hash Table: 时间复杂度O(n), 空间复杂度O(n)
Previous
599 Minimum Index Sum of Two Lists
Next
734 Sentence Similarity
Last modified
2yr ago
Copy link
Contents
697. Degree of an Array
1. Question
2. Implementation
3. Time & Space Complexity