Degree of an Array
找一个数组的最小的最高频子数组, 当有超过一个同样的高频时, 返回长度最小的子数组. 这个题就是先找到高频, 然后记录每个元素的左边和右边, 最后比较.
|
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 |
class Solution { public int findShortestSubArray(int[] nums) { Map<Integer, Integer> left = new HashMap<>(); Map<Integer, Integer> right = new HashMap<>(); Map<Integer, Integer> count = new HashMap<>(); for(int i = 0 ; i < nums.length; i++) { if(left.get(nums[i]) == null) left.put(nums[i], i); right.put(nums[i], i); count.put(nums[i], count.getOrDefault(nums[i], 0) + 1); } int max = Integer.MIN_VALUE; for(int n : count.values()) max = Math.max(max, n); int res = Integer.MAX_VALUE; for(int n : count.keySet()) { if(max == count.get(n)) { res = Math.min(res, right.get(n) - left.get(n) + 1); } } return res; } } |