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;
}```

```    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;
}      ```

0 条评论