LWC 54：697. Degree of an Array
LWC 54：697. Degree of an Array
LWC 54：697. Degree of an Array
Problem:
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: [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: [1,2,2,3,1,4,2] Output: 6
Note:
nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.
思路： 可以确定，答案一定是频次出现最多的元素，在数组中的最左边界和最右边界之差。当然频次出现最多的元素可能有多个，遍历一遍这些元素即可。
代码如下:
public int findShortestSubArray(int[] nums) {
if (!lf.containsKey(nums[i])) lf.put(nums[i], i);
rt.put(nums[i], i);
cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
}
int degree = Collections.max(cnt.values());
int ans = Integer.MAX_VALUE;
for (int key : cnt.keySet()) {
if (degree == cnt.get(key)) {
ans = Math.min(ans, rt. Map<Integer, Integer> lf = new HashMap<>();
Map<Integer, Integer> rt = new HashMap<>();
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
get(key) - lf.get(key) + 1);
}
}
return ans;
}尺取法
构造合法窗口，在合法窗口下更新最小长度。时间复杂度O(n)
可参考博文： http://blog.csdn.net/u014688145/article/details/73801021
代码如下：
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int key : map.keySet()) {
max = Math.max(max, map.get(key));
}
int ans = 1 << 29;
Map<Integer, Integer> cnt = new HashMap<>();
int lf = 0, rt = 0;
int window = 0;
for (;;) {
while (rt < nums.length && window != max) {
cnt.put(nums[rt], cnt.getOrDefault(nums[rt], 0) + 1);
window = Math.max(window, cnt.get(nums[rt]));
rt ++;
}
if (window != max) break;
ans = Math.min(ans, rt - lf);
cnt.put(nums[lf], cnt.get(nums[lf]) - 1);
lf ++;
window = Collections.max(cnt.values());
}
return ans;
}