LeetCode Solutions
697. Degree of an Array
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
int ans = 0;
int degree = 0;
unordered_map<int, int> debut;
unordered_map<int, int> count;
for (int i = 0; i < nums.size(); ++i) {
const int num = nums[i];
if (!debut.count(num))
debut[num] = i;
if (++count[num] > degree) {
degree = count[num];
ans = i - debut[num] + 1;
} else if (count[num] == degree) {
ans = min(ans, i - debut[num] + 1);
}
}
return ans;
}
};
class Solution {
public int findShortestSubArray(int[] nums) {
int ans = 0;
int degree = 0;
Map<Integer, Integer> debut = new HashMap<>();
Map<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
final int num = nums[i];
debut.putIfAbsent(num, i);
count.put(num, count.getOrDefault(num, 0) + 1);
if (count.get(num) > degree) {
degree = count.get(num);
ans = i - debut.get(num) + 1;
} else if (count.get(num) == degree) {
ans = Math.min(ans, i - debut.get(num) + 1);
}
}
return ans;
}
}
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
ans = 0
degree = 0
debut = {}
count = Counter()
for i, num in enumerate(nums):
debut.setdefault(num, i)
count[num] += 1
if count[num] > degree:
degree = count[num]
ans = i - debut[num] + 1
elif count[num] == degree:
ans = min(ans, i - debut[num] + 1)
return ans